← 返回题目列表

Codeforces · 383/C

C. 繁殖树

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

Iahub非常喜欢树。最近他发现了一棵有趣的树,名叫繁殖树。该树由编号为 1 到 n 的 n 个节点组成,每个节点 i 都有一个初始值 ai。树的根是节点 1。

这棵树有一个特殊的属性:当将值 val 添加到节点 i 的值时,值 -val 将添加到节点 i 的所有子节点的值。请注意,当您将值 -val 添加到节点 i 的子节点时,您还会将 -(-val) 添加到节点 i 的子节点的所有子节点,依此类推。查看示例解释以更好地理解它是如何工作的。

该树支持两种类型的查询:

- "1 x val" — val 添加到节点 x 的值;
- "2 x" — 打印节点 x 的当前值。

为了帮助Iahub更好地理解这棵树,您必须回答m个上述类型的查询。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 200000)。第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 1000)。接下来的 n–1 行中的每一行都包含两个整数 vi 和 ui (1 ≤ vi, ui ≤ n),这意味着节点 vi 和 ui 之间有一条边。

接下来的 m 行中的每一行都包含上述格式的查询。保证所有查询都满足以下约束:1 ≤ x ≤ n,1 ≤ val ≤ 1000。

输出

对于类型二的每个查询(打印节点 x 的值),您必须在单独的行上打印查询的答案。必须按照输入中给出的顺序回答查询。

示例

输入 #1

5 5
1 2 1 1 2
1 2
1 3
2 4
2 5
1 2 3
1 1 2
2 1
2 2
2 4

输出 #1

3
3
0

注意

节点的值开头为 [1, 2, 1, 1, 2]。

然后将值 3 添加到节点 2。它会传播,并将值 -3 添加到它的儿子节点 4 和节点 5。然后它无法再传播。所以节点的值为 [1, 5, 1, - 2, - 1]。

然后将值 2 添加到节点 1。它进行传播,并将值 -2 添加到它的儿子节点 2 和节点 3。它从节点 2 再次传播,将值 2 添加到它的儿子节点 4 和节点 5。节点 3 没有儿子,因此它无法从那里传播。节点的值为 [3, 3, - 1, 0, 1]。

您可以在以下链接查看有关树的所有定义:http://en.wikipedia.org/wiki/Tree_(graph_theory)