分数: 400 点
问题陈述
给定是一棵有根树 N 顶点编号 1 to N。 根是顶点 1,以及 i第边缘 (1 \leq i \leq N - 1) 连接顶点 a_i 和 b_i.
每个顶点都安装了一个计数器。最初,所有顶点上的计数器都有值 0.
现在,以下 将执行 Q 操作:
- 操作 j (1 \leq j \leq Q):增加 x_j 以 Vertex 为根的子树中包含的每个顶点的计数器 p_j.
在所有操作之后查找每个顶点上的计数器的值。
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq a_i < b_i \leq N
- 1 \leq p_j \leq N
- 1 \leq x_j \leq 10^4
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q
输出
打印 Vertex 上计数器的值 1, 2, \ldots, N 在所有操作之后,按此顺序,中间有空格。
示例输入 1
4 3 1 2 2 3 2 4 2 10 1 100 3 1
示例输出 1
100 110 111 110
该输入中的树如下:

每个操作都会更改顶点上计数器的值,如下所示:
- 操作 1:增加 10 以 Vertex 为根的子树中包含的每个顶点的计数器 2,即顶点 2, 3, 4。 Vertex 上计数器的值 1, 2, 3, 4 现在 0, 10, 10, 10。
- 操作 2:增加 100 以 Vertex 为根的子树中包含的每个顶点的计数器 1,即顶点 1, 2, 3, 4。 Vertex 上计数器的值 1, 2, 3, 4 现在 100, 110, 110, 110。
- 操作 3:增加 1 以 Vertex 为根的子树中包含的每个顶点的计数器 3,即顶点 3。 Vertex 上计数器的值 1, 2, 3, 4 现在 100, 110, 111, 110。
示例输入 2
6 2 1 2 1 3 2 4 3 6 2 5 1 10 1 10
示例输出 2
20 20 20 20 20 20