树上区间加 & 点查（Vertex Get Range Add on Tree）

问题描述

给定一棵含 $N$ 个顶点的树，第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。
初始时，每个顶点 $i$ 上有一个值 $a_i$。

处理 $Q$ 个查询，类型如下：

• 0 p l r x：对所有满足 到顶点 $p$ 的距离 $\in [l, r)$ 的顶点 $i$，执行 $a_i \leftarrow a_i + x$。
• 1 p：输出顶点 $p$ 当前的值 $a_p$。

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $-10^9 \leq a_i \leq 10^9$
• $0 \leq u_i, v_i \leq N-1$
• $0 \leq p \leq N-1$
• $0 \leq l < r \leq N$
• $-10^9 \leq x \leq 10^9$

输入

$N\ Q$
$a_0\ a_1\ \cdots\ a_{N-1}$
$u_0\ v_0$
$u_1\ v_1$
:
$u_{N-2}\ v_{N-2}$
Query₀
Query₁
:
Query$_{Q-1}$

9 16
1 10 100 1000 10000 100000 1000000 10000000 100000000
0 1
1 2
1 3
3 4
3 5
0 6
6 7
6 8
0 0 1 3 1
1 0
1 1
1 7
1 4
0 3 0 9 10
1 2
1 3
0 6 1 2 100
1 6
1 7
1 0
1 1
0 2 5 9 100
1 5
1 8

1
11
10000001
10000
111
1011
1000011
10000111
111
21
100010
100000111

1 3
1
1 0
0 0 0 1 10
1 0

1
11