← 返回题目列表

Codeforces · 916/E

E. 杰米和树

中文机器翻译题面 查看原题

令你惊讶的是,杰米是最终的老板!呃呃呃。

Jamie 给了你一棵有 n 个顶点的树,编号从 1 到 n。最初,树的根是编号为 1 的顶点。此外,每个顶点都有一个值。

Jamie 还为您提供了三种类型的树查询:

1 v — 将树的根更改为编号为 v 的顶点。

2 u v x — 对于包含 u 和 v 的最小尺寸子树中的每个顶点,将 x 添加到其值。

3 v — 求编号为 v 的顶点的子树中顶点值的总和。

顶点 v 的子树是一组顶点,使得 v 位于从该顶点到树根的最短路径上。请注意,更改树的根后,顶点的子树也会更改。

通过准确执行查询向 Jamie 展示您的编程实力!

输入

输入的第一行包含两个空格分隔的整数 n 和 q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) - 分别是树中的顶点数和要处理的查询数。

第二行包含 n 个空格分隔的整数 a1, a2, ..., an (- 108 ≤ ai ≤ 108) - 顶点的初始值。

接下来的 n - 1 行包含两个空格分隔的整数 ui, vi (1 ≤ ui, vi ≤ n) 描述树中顶点 ui 和 vi 之间的边。

以下 q 行描述了查询。

每个查询根据其类型具有以下格式之一:

1 v (1 ≤ v ≤ n) 对于第一类型的查询。

2 u v x (1 ≤ u, v ≤ n, - 108 ≤ x ≤ 108) 对于第二类型的查询。

3 v (1 ≤ v ≤ n) 用于第三类查询。

查询描述中的所有数字均为整数。

查询必须按照给定的顺序执行。保证树是有效的。

输出

对于第三种类型的每个查询,输出所需的答案。保证 Jamie 至少给出一个第三类型的查询。

示例

输入 #1

6 7
1 4 2 8 5 7
1 2
3 1
4 3
4 5
3 6
3 1
2 4 6 3
3 4
1 6
2 2 4 -5
1 4
3 3

输出 #1

27
19
5

输入 #2

4 6
4 3 5 6
1 2
2 3
3 4
3 1
1 3
2 2 4 3
1 1
2 2 4 -3
3 1

输出 #2

18
21

注意

下图显示了第一个示例中的查询后树的变化情况。