D - Ki Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

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 を足す。

すべての操作のあとの各頂点のカウンターの値を求めてください。

制約

  • 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 の順に空白区切りで出力せよ。

入力例 1

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

出力例 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 となる。

入力例 2

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

出力例 2

20 20 20 20 20 20

Score : 400 points

Problem Statement

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.

Constraints

  • 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
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
:
a_{N-1} b_{N-1}
p_1 x_1
:
p_Q x_Q

Output

Print the values of the counters on Vertex 1, 2, \ldots, N after all operations, in this order, with spaces in between.

Sample Input 1

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

Sample Output 1

100 110 111 110

The tree in this input is as follows:

Figure

Each operation changes the values of the counters on the vertices as follows:

  • Operation 1: Increment by 10 the counter on every vertex contained in the subtree rooted at Vertex 2, that is, Vertex 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 0, 10, 10, 10, respectively.
  • Operation 2: Increment by 100 the counter on every vertex contained in the subtree rooted at Vertex 1, that is, Vertex 1, 2, 3, 4. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 110, 110, respectively.
  • Operation 3: Increment by 1 the counter on every vertex contained in the subtree rooted at Vertex 3, that is, Vertex 3. The values of the counters on Vertex 1, 2, 3, 4 are now 100, 110, 111, 110, respectively.

Sample Input 2

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

Sample Output 2

20 20 20 20 20 20