AT_past202010_m 筆塗り

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。有 $N-1$ 条边，编号为 $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$ 的最终颜色。

输入以如下格式从标准输入读入。 > $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$ 条边最终的颜色。

### 注意 本题在 2020/11/8 18:00 JST 之前禁止讨论。如果有讨论，可能会被要求赔偿。考试结束后可以公开总分和认证等级，但请不要透露解题情况等信息。 ### 约束条件 - 所有输入均为整数。 - $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$ - 给定的图为树。 ### 样例说明 1 - 初始时，所有边的颜色均为 $0$。 - 第 $1$ 次操作将边 $1$、$2$ 的颜色覆盖为 $10$。 - 第 $2$ 次操作将边 $1$ 的颜色覆盖为 $5$。 - 最终，边 $1,2,3$ 的颜色分别为 $5,10,0$。 由 ChatGPT 4.1 翻译