分数: 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