D - Ki

分数: $400$ 分

问题描述

给定一个有 $N$ 个节点 (编号从 $1$ 到 $N$) 的有根树。 根节点是节点 $1$，第 $i$ 条边 $(1 \leq i \leq N - 1)$ 连接节点 $a_i$ 和 $b_i$。

每个节点上都安装了一个计数器。初始时，所有节点上的计数器的值为 $0$。

现在，将进行以下 $Q$ 次操作:

• 操作 $j$ $(1 \leq j \leq Q)$: 将以节点 $p_j$ 为根的子树中的每个节点的计数器增加 $x_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$

输出

按顺序输出每个节点 $1, 2, \ldots, N$ 上计数器的值，并用空格分隔。

4 3
1 2
2 3
2 4
2 10
1 100
3 1

100 110 111 110

该输入中的树如下图所示:

每次操作改变节点上计数器的值如下:

• 第 $1$ 次操作: 将以节点 $2$ 为根的子树中的每个节点的计数器增加 $10$，即节点 $2, 3, 4$ 的计数器值变为 $10$。节点 $1, 2, 3, 4$ 的计数器值变为 $0, 10, 10, 10$。
• 第 $2$ 次操作: 将以节点 $1$ 为根的子树中的每个节点的计数器增加 $100$，即节点 $1, 2, 3, 4$ 的计数器值变为 $110$。节点 $1, 2, 3, 4$ 的计数器值变为 $100, 110, 110, 110$。
• 第 $3$ 次操作: 将以节点 $3$ 为根的子树中的每个节点的计数器增加 $1$，即节点 $3$ 的计数器值变为 $111$。节点 $1, 2, 3, 4$ 的计数器值变为 $100, 110, 111, 110$。

6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10

20 20 20 20 20 20