E - Through Path Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

N 頂点 N-1 辺から成る木があり、頂点には 1, 2, \dots, N の番号が、辺には 1, 2, \dots, N-1 の番号がついています。辺 i は頂点 a_i と頂点 b_i を結びます。 この木の各頂点には 1 つの整数が書かれています。頂点 i に書かれている整数を c_i とします。はじめ、 c_i = 0 です。

Q 個のクエリが与えられます。 i 番目のクエリでは、整数 t_i, e_i, x_i が与えられます。クエリの内容は以下の通りです。

  • t_i = 1 のとき : 頂点 a_{e_i} から辺をたどって頂点 b_{e_i} を通らずに到達できるような全ての頂点 v に対して、c_v を c_v + x_i に書き換える。
  • t_i = 2 のとき : 頂点 b_{e_i} から辺をたどって頂点 a_{e_i} を通らずに到達できるような全ての頂点 v に対して、c_v を c_v + x_i に書き換える。

すべてのクエリを処理した後、各頂点に書かれた整数を出力してください。

制約

  • 入力は全て整数
  • 2 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • 与えられるグラフは木である
  • 1 \le Q \le 2 \times 10^5
  • t_i \in \{1, 2\}
  • 1 \le e_i \le N-1
  • 1 \le x_i \le 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
t_1 e_1 x_1
\vdots
t_Q e_Q x_Q

出力

すべてのクエリを処理した後の c_1, c_2, \dots, c_N をこの順に改行区切りで出力せよ。

入力例 1

5
1 2
2 3
2 4
4 5
4
1 1 1
1 4 10
2 1 100
2 2 1000

出力例 1

11
110
1110
110
100

1 番目のクエリでは、頂点 1 から始めて頂点 2 を通らずに到達できる頂点 1 に 1 を足します。
2 番目のクエリでは、頂点 4 から始めて頂点 5 を通らずに到達できる頂点 1, 2, 3, 4 に 10 を足します。
3 番目のクエリでは、頂点 2 から始めて頂点 1 を通らずに到達できる頂点 2, 3, 4, 5 に 100 を足します。
4 番目のクエリでは、頂点 3 から始めて頂点 2 を通らずに到達できる頂点 3 に 1000 を足します。

入力例 2

7
2 1
2 3
4 2
4 5
6 1
3 7
7
2 2 1
1 3 2
2 2 4
1 6 8
1 3 16
2 4 32
2 1 64

出力例 2

72
8
13
26
58
72
5

入力例 3

11
2 1
1 3
3 4
5 2
1 6
1 7
5 8
3 9
3 10
11 4
10
2 6 688
1 10 856
1 8 680
1 8 182
2 2 452
2 4 183
2 6 518
1 3 612
2 6 339
2 3 206

出力例 3

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559

Score : 500 points

Problem Statement

We have a tree with N vertices and N-1 edges, where the vertices are numbered 1, 2, \dots, N and the edges are numbered 1, 2, \dots, N-1. Edge i connects Vertices a_i and b_i.
Each vertex in the tree has an integer written on it. Let c_i be the integer written on Vertex i. Initially, c_i = 0.

You will be given Q queries. The i-th query, consisting of integers t_i, e_i, and x_i, is as follows:

  • If t_i = 1: for each Vertex v reachable from Vertex a_{e_i} without visiting Vertex b_{e_i} by traversing edges, replace c_v with c_v + x_i.
  • If t_i = 2: for each Vertex v reachable from Vertex b_{e_i} without visiting Vertex a_{e_i} by traversing edges, replace c_v with c_v + x_i.

After processing all queries, print the integer written on each vertex.

Constraints

  • All values in input are integers.
  • 2 \le N \le 2 \times 10^5
  • 1 \le a_i, b_i \le N
  • The given graph is a tree.
  • 1 \le Q \le 2 \times 10^5
  • t_i \in \{1, 2\}
  • 1 \le e_i \le N-1
  • 1 \le x_i \le 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}
Q
t_1 e_1 x_1
\vdots
t_Q e_Q x_Q

Output

Print the values c_1, c_2, \dots, c_N after processing all queries, each in its own line.

Sample Input 1

5
1 2
2 3
2 4
4 5
4
1 1 1
1 4 10
2 1 100
2 2 1000

Sample Output 1

11
110
1110
110
100

In the first query, we add 1 to each vertex reachable from Vertex 1 without visiting Vertex 2, that is, Vertex 1.
In the second query, we add 10 to each vertex reachable from Vertex 4 without visiting Vertex 5, that is, Vertex 1, 2, 3, 4.
In the third query, we add 100 to each vertex reachable from Vertex 2 without visiting Vertex 1, that is, Vertex 2, 3, 4, 5.
In the fourth query, we add 1000 to each vertex reachable from Vertex 3 without visiting Vertex 2, that is, Vertex 3.

Sample Input 2

7
2 1
2 3
4 2
4 5
6 1
3 7
7
2 2 1
1 3 2
2 2 4
1 6 8
1 3 16
2 4 32
2 1 64

Sample Output 2

72
8
13
26
58
72
5

Sample Input 3

11
2 1
1 3
3 4
5 2
1 6
1 7
5 8
3 9
3 10
11 4
10
2 6 688
1 10 856
1 8 680
1 8 182
2 2 452
2 4 183
2 6 518
1 3 612
2 6 339
2 3 206

Sample Output 3

1657
1657
2109
1703
1474
1657
3202
1474
1247
2109
2559