Description
江湖由 N 个门派（2≤N≤100,000，编号从 1 到 N）组成，这些门派之间有 N-1 条小道将他们连接起来，每条道路都以“尺”为单位去计量，武林盟主发现任何两个门派都能够直接或者间接通过小道连接。
虽然整个江湖是可以互相到达的，但是他担心有心怀不轨之徒破坏这个武林的安定，破坏小道，于是武林盟主又秘密地修建了 M 条密道（1≤M≤100,000），但每条小道距离都不超过10亿尺。
果不其然，最近一个名叫“太吾”的组织意欲破坏武林的小道，请你帮盟主想想办法，如果门派 A 到门派 B 的直连小道被破坏，从 A 走到 B 的所有路径中，经过密道的距离最少是多少？
虽然整个江湖是可以互相到达的，但是他担心有心怀不轨之徒破坏这个武林的安定，破坏小道，于是武林盟主又秘密地修建了 M 条密道（1≤M≤100,000），但每条小道距离都不超过10亿尺。
果不其然，最近一个名叫“太吾”的组织意欲破坏武林的小道，请你帮盟主想想办法，如果门派 A 到门派 B 的直连小道被破坏，从 A 走到 B 的所有路径中，经过密道的距离最少是多少？
Input
第一行数字 N M
接下来 N-1 行，每行两个整数 A B，表示 A-B 间有一条直连小道
接下来 M 行，每行三个数字 A B V，表示 A-B 间有一条代价为 V 的密道
接下来 N-1 行，每行两个整数 A B，表示 A-B 间有一条直连小道
接下来 M 行，每行三个数字 A B V，表示 A-B 间有一条代价为 V 的密道
Output
输出 N-1 行，对应原输入的小道，每个小道被破坏后，最少需要经过多长的密道？如果不存在替换的道路，请输出-1
Sample Input
6 3
4 1
1 3
4 5
1 2
6 5
3 6 8
2 3 7
6 4 5
Sample Input
6 3
4 1
1 3
4 5
1 2
6 5
3 6 8
2 3 7
6 4 5
Data Constraint
30%数据：N<=300,M<=1000
50%数据：N<=1000,M<=1000
70%数据：N<=5000,M<=5000
对于另外15%的数据点：树是一条链
100%数据：N,M<=100,000
50%数据：N<=1000,M<=1000
70%数据：N<=5000,M<=5000
对于另外15%的数据点：树是一条链
100%数据：N,M<=100,000
做法：将所有密道按照权值从小到大排序。 对于一条密道(u,v,w)，如果u到v的路径上的边中存在边之前还没有被覆盖过，那么说明这条边的答案就是w. 可以用并查集维护，维护每个集合深度最小的节点，对于密道(u,v,w)，每次u都在它所在集合中找到深度最小的 点，这个点与父亲的连边一定就是上述的边，将这条边的答案更新为w，然后将这个节点与其父亲合并，直到u所 在集合的深度最小的节点是小于u和v的lca的，对v做同样的过程即可。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define N 100007
using namespace std;
struct edge{
int x,to,next;
int w,id;
}e[*N];
struct arr{
int x,y;
int w;
}a[*N];
int n,m,ls[N],tot,f[N],fa[N][],dep[N],cnt;
int c[N],ans[N]; void add(int x,int y,int id){
e[++tot].to=y;
e[tot].x=x;
e[tot].id=id;
e[tot].next=ls[x];
ls[x]=tot;
} void Init(){
scanf("%d%d",&n,&m);
for (int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v,i);
add(v,u,i);
}
for (int i=;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);
for (int i=;i<=n;i++) f[i]=i;
} int find(int x){
if (f[x]==x) return x;
return f[x]=find(f[x]);
} void Dfs(int x,int pre){
fa[x][]=pre;
dep[x]=dep[pre]+;
for (int i=ls[x];i;i=e[i].next){
int v=e[i].to;
if (v==pre) continue;
c[v]=e[i].id;
Dfs(v,x);
}
} int cmp(arr x,arr y){
return x.w<y.w;
}
void Work(){
sort(a+,a+m+,cmp);
for (int i=;i<=m;i++){
int u=a[i].x,v=a[i].y;
int q=find(u);
int p=find(v);
while (q!=p){
if (dep[q]<dep[p]) swap(q,p);
ans[c[q]]=a[i].w;
q=f[q]=find(fa[q][]);
}
}
for (int i=;i<n;i++) if (ans[i]!=) printf("%d\n",ans[i]); else printf("-1\n");
} int main(){
freopen("worry.in","r",stdin);
freopen("worry.out","w",stdout);
Init();
Dfs(,);
Work();
}