← 返回题目列表

AtCoder · abc138_d

D. 基

中文机器翻译题面 查看原题

分数: 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

该输入中的树如下:

Figure

每个操作都会更改顶点上计数器的值,如下所示:

  • 操作 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