计数器

题目描述

给定一个具有 $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$。

求所有操作结束后，每个顶点的计数器值。

输入格式

输入按以下格式从标准输入给出：

$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$ 为根的子树中包含的所有顶点，即顶点 $2, 3, 4$ 的计数器值加上 $10$。顶点 $1, 2, 3, 4$ 的计数器值分别变为 $0, 10, 10, 10$。
• 操作 $2$：将以顶点 $1$ 为根的子树中包含的所有顶点，即顶点 $1, 2, 3, 4$ 的计数器值加上 $100$。顶点 $1, 2, 3, 4$ 的计数器值分别变为 $100, 110, 110, 110$。
• 操作 $3$：将以顶点 $3$ 为根的子树中包含的所有顶点，即顶点 $3$ 的计数器值加上 $1$。顶点 $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

数据范围

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq a_i \lt b_i \leq N$
• $1 \leq p_j \leq N$
• $1 \leq x_j \leq 10^4$
• 给定的图是一棵树
• 输入中的所有值均为整数