You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

这是一道模板题。

本题严重卡常，请务必使用 fread 快读，不保证无快读的程序能过（虽然标程没用快读）。另外，建议使用 Tarjan 或树剖求 LCA。

给一棵有根树，这棵树由编号为 $1\dots N$ 的 $N$ 个结点组成。根结点的编号为 $R$。每个结点都有一个权值，结点 $i$ 的权值为 $v_i$。
接下来有 $M$ 组操作，操作分为三类：

• 1 a x，表示将结点 $a$ 的权值增加 $x$；
• 2 a x，表示将 $a$ 的子树上所有结点的权值增加 $x$；
• 3 a b，表示求「结点 $a$ 到结点 $b$ 的简单路径」上所有结点的权值之和。

输入格式

第一行有三个整数 $N,M$ 和 $R$。
第二行有 $N$ 个整数，第 $i$ 个整数表示 $v_i$。
在接下来的 $N-1$ 行中，每行两个整数，表示一条边。
在接下来的 $M$ 行中，每行一组操作。

输出格式

对于每组 $\texttt{3 a b}$ 操作，输出一个整数，表示「结点 $a$ 到结点 $b$ 的简单路径」上所有结点的权值之和（含结点 $a,$ $b$）。

10 13 5
-2 -7 0 2 -9 -2 -4 9 8 -1
9 8
9 4
9 2
4 10
10 7
10 6
2 1
8 3
7 5
3 8 6
1 7 -8
1 5 -9
1 5 -4
1 4 -2
1 2 -1
3 5 1
1 7 1
3 1 3
1 1 -3
3 10 2
1 1 -8
3 8 4

16
-37
7
-1
17

提示

$40\%$ 的数据不含操作 3。
对于所有数据，$1\leqslant N, M\leqslant 10^6,$ $1\leqslant R\leqslant N,$ $-10^6\leqslant v_i, x\leqslant 10^6$.