点加树上等距层求和

【题目描述】

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

• 0 $p$ $x$：$a_p \leftarrow a_p+x$
• 1 $p$ $l$ $r$：输出与顶点 $p$ 的距离在 $[l,r)$ 内的顶点上写有的值之和。

【输入】

$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$ $l$ $r$ 查询，输出一行一个整数，表示对应的值之和。

【输入样例】

9 12
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
1 0 2 3
1 1 1 3
1 6 2 4
1 2 0 1
1 8 6 9
0 0 999999999
1 0 2 3
1 4 0 3
0 6 -999999
0 4 990000
1 3 1 3
1 7 0 5

【输出样例】

110001100
1111101
1110
100
0
110001100
111010
1001100110
1110001111

【输入样例2】

1 2
1
0 0 1
1 0 0 1

【输出样例2】

2

【数据范围】

• $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$
• $-1000000000 \leq x \leq 1000000000$
• $0 \leq l \lt r \leq N$

【来源】

Library Checker（yosupo06） vertex_add_range_contour_sum_on_tree