← 返回题目列表

AtCoder · past202010_m

M. 刷画

中文机器翻译题面 查看原题

分数: 6 点

警告

2020 年 11 月 8 日下午 6:00 之前请勿提及此问题。日本标准时间。如有违反,可要求赔偿。 考试结束后,您可以向其他人透露您的总分和成绩,但仅此而已(例如,您解决了哪些问题)。

问题陈述

给定的是一棵树 N 顶点编号 1 通过 N。 这棵树有 N-1 边编号 1 通过 N-1和边缘 i 连接顶点 a_i 和 b_i 双向。 每条边都可以涂上由之间的整数表示的颜色 0 和 10^5 (含)。 最初,每个边缘都涂有颜色 0.

Q 操作将在此树上完成。在 i-th 操作,从 Vertex 开始的最短路径上每条边的颜色 u_i 到顶点 v_i 变为颜色 c_i.

检查边缘的颜色 1, 2, \ldots, N-1 之后 Q 操作。

约束

  • 输入中的所有值都是整数。
  • 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第行应包含 Edge 的颜色 i 已涂漆。


示例输入 1

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

示例输出 1

5
10
0
  • 最初,每个边缘都涂有颜色 0.
  • 在第一个操作中,Edge 1 和边缘 2 重新涂上颜色 10.
  • 在第二次操作中,Edge 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