M - 筆塗り Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 6 点

注意

この問題に対する言及は、2020/11/8 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。

問題文

1 から N の番号がついた N 個の頂点からなる木が与えられます。 1 から N-1 の番号がついた N-1 本の辺があり、辺 i は頂点 a_i と頂点 b_i を双方向につないでいます。 それぞれの辺には色を塗ることができます。色は 0 以上 10^5 以下の整数で表されます。 はじめ、全ての辺は色 0 で塗られています。

この木に対して、Q 回操作が行われます。i 回目の操作では、頂点 u_i と頂点 v_i の最短経路上にある辺の色が全て色 c_i で上書きされます。

Q 回の操作後、辺 1,2,\ldots,N-1 がどの色で塗られているかを調べてください。

制約

  • 与えられる入力は全て整数
  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq a_i, b_i,u_i,v_i \leq N
  • u_i \neq v_i
  • 1 \leq c_i \leq 10^5
  • 与えられるグラフは木

入力

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

N Q
a_1 b_1
\vdots
a_{N-1} b_{N-1}
u_1 v_1 c_1
\vdots
u_Q v_Q c_Q

出力

N-1 行出力せよ。i 行目では、辺 i に塗られている色を出力せよ。

入力例 1

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

出力例 1

5
10
0
  • はじめ、全ての辺は色 0 で塗られています。
  • 1 回目の操作では辺 1、2 の色が色 10 で上書きされます。
  • 2 回目の操作では辺 1 の色が色 5 で上書きされます。
  • 最終的に辺 1,2,3 はそれぞれ、5,10,0 で塗られています。

入力例 2

10 10
7 2
5 8
8 6
8 3
8 9
9 1
4 8
4 10
8 7
7 5 12773
2 6 74733
1 6 64470
7 2 41311
1 9 39776
4 8 71709
9 1 23551
4 6 29181
3 7 23742
8 4 54686

出力例 2

41311
12773
29181
23742
64470
23551
54686
0
23742

Score : 6 points

Warning

Do not make any mention of this problem until November 8, 2020, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).

Problem Statement

Given is a tree with N vertices numbered 1 through N. The tree has N-1 edges numbered 1 through N-1, and Edge i connects Vertex a_i and b_i bidirectionally. Each edge can be painted in a color represented by an integer between 0 and 10^5 (inclusive). Initially, every edge is painted in Color 0.

Q operations will be done on this tree. In the i-th operation, the color of every edge on the shortest path from Vertex u_i to Vertex v_i becomes Color c_i.

Examine the color of the edges 1, 2, \ldots, N-1 after the Q operations.

Constraints

  • All values in input are integers.
  • 2 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq a_i, b_i,u_i,v_i \leq N
  • u_i \neq v_i
  • 1 \leq c_i \leq 10^5
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N Q
a_1 b_1
\vdots
a_{N-1} b_{N-1}
u_1 v_1 c_1
\vdots
u_Q v_Q c_Q

Output

Print N-1 lines. The i-th line should contain the color in which Edge i is painted.

Sample Input 1

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

Sample Output 1

5
10
0
  • Initially, every edge is painted in Color 0.
  • In the first operation, Edge 1 and Edge 2 are repainted in Color 10.
  • In the second operation, Edge 1 is repainted in Color 5.
  • In the end, the edges 1, 2, and 3 are painted in Color 5, 10, and 0, respectively.

Sample Input 2

10 10
7 2
5 8
8 6
8 3
8 9
9 1
4 8
4 10
8 7
7 5 12773
2 6 74733
1 6 64470
7 2 41311
1 9 39776
4 8 71709
9 1 23551
4 6 29181
3 7 23742
8 4 54686

Sample Output 2

41311
12773
29181
23742
64470
23551
54686
0
23742