题目描述

Given is a rooted tree with $N$ vertices numbered $1$ to $N$. The root is Vertex $1$, and the $i$-th edge $(1 \leq i \leq N - 1)$ connects Vertex $a_i$ and $b_i$.

Each of the vertices has a counter installed. Initially, the counters on all the vertices have the value $0$.

Now, the following $Q$ operations will be performed:

• Operation $j$ $(1 \leq j \leq Q)$: Increment by $x_j$ the counter on every vertex contained in the subtree rooted at Vertex $p_j$.

Find the value of the counter on each vertex after all operations.

给出一棵有根的树，树上有 $N$ 个顶点，编号为 $1$ 至 $N$ 。根是顶点 $1$ ，边 $i$ 连接顶点 $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$ 上所有操作后的计数器值，中间留空格。

样例 #1

样例输入 #1

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

样例输出 #1

100 110 111 110

样例 #2

样例输入 #2

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

样例输出 #2

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$
• 给定图形是一棵树。
• 输入值均为整数。

样例 $1$ 解释

该输入的树形结构如下

每次操作都会改变顶点上计数器的值，具体如下：

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