树上等距层加点查询

【题目描述】

给定一棵有 $N$ 个顶点的树，其中第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。初始时顶点 $i$ 上写有一个值 $a_i$。依次处理以下 $Q$ 个查询：

• 0 $p$ $l$ $r$ $x$：对所有与顶点 $p$ 的距离属于 $[l,r)$ 的顶点 $i$，令 $a_i \leftarrow a_i+x$。
• 1 $p$：输出 $a_p$。

【输入】

$N$ $Q$
$a_0$ $\cdots$ $a_{N-1}$
$u_0$ $v_0$
$\vdots$
$u_{N-2}$ $v_{N-2}$
$\mathrm{Query}_0$
$\vdots$
$\mathrm{Query}_{Q-1}$

【输出】

对每个 1 $p$ 查询，输出一行一个整数，表示 $a_p$。

【输入样例】

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

【输入样例2】

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

【输出样例2】

1
11

【数据范围】

• $1 \leq N \leq 100000$
• $1 \leq Q \leq 200000$
• $-1000000000 \leq a_i \leq 1000000000$
• $0 \leq u_i, v_i \leq N-1$
• $0 \leq p \leq N-1$
• $0 \leq l \lt r \leq N$
• $-1000000000 \leq x \leq 1000000000$

【来源】

Library Checker（yosupo06） vertex_get_range_contour_add_on_tree