[并查集] Jzoj P5914 盟主的忧虑

Description

江湖由 N 个门派（2≤N≤100,000，编号从 1 到 N）组成，这些门派之间有 N-1 条小道将他们连接起来，每条道路都以“尺”为单位去计量，武林盟主发现任何两个门派都能够直接或者间接通过小道连接。
虽然整个江湖是可以互相到达的，但是他担心有心怀不轨之徒破坏这个武林的安定，破坏小道，于是武林盟主又秘密地修建了 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 的密道

Output

输出 N-1 行，对应原输入的小道，每个小道被破坏后，最少需要经过多长的密道？如果不存在替换的道路，请输出-1

Sample Input

Sample Output

Data Constraint

30%数据：N<=300,M<=1000
50%数据：N<=1000,M<=1000
70%数据：N<=5000,M<=5000
对于另外15%的数据点：树是一条链
100%数据：N,M<=100,000

题解

显然只会走一条非树边
我们枚举一条非树边，能够以这条边为答案的树边一定在非树边两端点的路径上
注意到区间取max取min非常难写于是我们可以对非树边排序，从大到小排序，那么每次就直接覆盖就好了，因为每次只会最优
可以用并查集，我们加树边等价于把两端点到它们lca路径上的边缩起来，表明这些边不会再更新答案了

代码

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <queue>
 4 #include <cstring>
 5 #include <algorithm> 
 6 #define N 100010
 7 using namespace std;
 8 struct edge{int to,from,w;}e[N*2];
 9 struct node{int x,y,v;}Q[N];
10 int n,m,cnt,fa[N],dep[N],k[N],d[N],p[N],head[N],father[N];
11 void insert(int x,int y,int z) { e[++cnt].to=y; e[cnt].from=head[x]; e[cnt].w=z; head[x]=cnt; }
12 int getfather(int x) { return father[x]?father[x]=getfather(father[x]):x; }
13 void dfs(int x,int pre)
14 {
15     fa[x]=pre,dep[x]=dep[pre]+1; 
16     for (int i=head[x];i;i=e[i].from) if (e[i].to!=pre) p[e[i].to]=e[i].w,dfs(e[i].to,x);
17 }
18 void work(int &x,int y) { d[p[x]]=y,father[x]=getfather(fa[x]),x=father[x]; }
19 bool cmp(node a,node b) { return a.v<b.v; }
20 int main()
21 {
22     freopen("worry.in","r",stdin),freopen("worry.out","w",stdout);
23     scanf("%d%d",&n,&m);
24     for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),insert(x,y,i),insert(y,x,i),d[i]=-1;
25     for (int i=1,x,y,z;i<=m;i++) scanf("%d%d%d",&Q[i].x,&Q[i].y,&Q[i].v);    
26     dfs(1,0),sort(Q+1,Q+m+1,cmp);
27     for (int i=1;i<=m;i++)
28     {
29         int x=getfather(Q[i].x),y=getfather(Q[i].y);
30         while (x!=y) work(dep[x]<dep[y]?y:x,Q[i].v);
31     }
32     for (int i=1;i<n;i++) printf("%d
",d[i]);
33 }