令你惊讶的是,杰米是最终的老板!呃呃呃。
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
注意
下图显示了第一个示例中的查询后树的变化情况。