题目描述

$1$ から $N$ までの番号がついた $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$ の順に空白区切りで出力せよ。

题目大意

给出一棵以$1$为根的树，有$N$个点，每个点上有一个计数器，初始$0$

接下来$Q$次操作，每次操作讲$p_i$的子树中所有点的计数器增加$x_i$

输出最后每个点的计数器值

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

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\ <\ b_i\ \leq\ N$
• $1\ \leq\ p_j\ \leq\ N$
• $1\ \leq\ x_j\ \leq\ 10^4$
• 与えられるグラフは木である。
• 入力中の値はすべて整数である。

Sample Explanation 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$ となる。