顶点加区间轮廓和（Vertex Add Range Contour Sum on Tree）

问题描述

给定一棵含 $N$ 个顶点的树，边为 $(u_i, v_i)$。每个顶点 $i$ 上初始写有值 $a_i$。
请按顺序处理以下 $Q$ 个查询：

• 0 p x：将顶点 $p$ 上的值增加 $x$（即 $a_p \leftarrow a_p + x$）。
• 1 p l r：输出所有满足 到顶点 $p$ 的距离 $d$ 满足 $l \le d < r$ 的顶点上的值之和。

注：距离指简单路径上的边数；$d(p, p) = 0$。

约束条件

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

输入格式

$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_0$
$Query_1$
:
$Query_{Q-1}$

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

1 2
1
0 0 1
1 0 0 1

2