C-石老板心肌梗塞_第二届天元编程邀请赛（提高组）

石老板心肌梗塞

比赛主页

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

石老板在上课时突然晕倒了，十万火急，你必须解出这道题，然后抢救石老板......

给定 $n$ 个节点的一棵树，同时给定 $m$ 条树上路径，每条路径带有一个权值 $w_i$ 。

同时树的 $n - 1$ 条边按照输入的顺序从 $1$ 到 $n - 1$ 标号。

现在规定记 $S_u$ 表示不包含第 $u$ 条树边的且属于给定的 $m$ 条路径的路径集合。

对于 $\forall$ $u \in[1,n - 1]$ ，求如下的答案： $\displaystyle \operatorname{mex}_{i \in S_u} w_i$

自然语言解释为：对于每一条树边求 $m$ 条路径中不经过它的路径的权值集合的 $\operatorname{mex}$

这里的 $\operatorname{mex}$ 指的是最小的没有出现的正整数。

同时并不保证所有的路径不重复，也就是可能对于同一组 $u,v$ 会有多组路径！保证 $u \ne v$ 。

输入描述:

第一行 $n,m$ 意义如上。

接下来 $n - 1$ 行每行给出 $u,v$ 表示 $u,v$ 之间有一条边。

再接下来 $m$ 行每行给出 $s,t,w$ 表示有一条从树上 $s$ 号点到 $t$ 号点的权值为 $w$ 的简单路径。

ps. 简单路径指的是没有环的路径。

输出描述:

 行，第  行对应不经过第  条边的答案

示例1

输入

复制

输出

复制

备注:

数据范围

存在 $20\%$ 的数据满足 $1 \leq n,m\leq 3000$

存在另外 $28 \%$ 的数据保证：形成的树是一条链，并且链的一端是 $1$ 号节点。

对于 $80 \%$ 的数据保证： $1 \leq n,m\leq 10^5$

对于 $100 \%$ 的数据保证： $1\le n \leq 5 \times 10^5, m \leq 2\times 10 ^ 6,1 \leq w_i \leq m$

大样例链接: https://pan.baidu.com/s/1uR8keXNeZmYLN46rMZ0Mfg 密码: a3tl

ex_treemex2.in/ex_treemex2.ans 对应 $20\%$ 数据的部分。

ex_treemex3.in/ex_treemex3.ans 对应另外 $28\%$ 数据的部分。