题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2001
cdq分治+重建图。
可以保留当前一定会被选的非修改边然后把点缩起来。这样的话每次点数至多只有r-l+1个，边数只有2*(r-l+1)-1个（生成树+修改边）。
时间复杂度O(nlog^2(n))
#include<cstring> #include<iostream> #include<cstdio> #include<algorithm> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 50050 #define ll long long #define inf 1000000000 using namespace std; struct data{int x,y;ll z;int k,id; }a[35][maxn]; struct node{int k;ll w;int id; }b[maxn]; int fa[maxn],pos[maxn],p[maxn],n,m,Q; ll dis[maxn]; int read(){ int x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } int find(int x){ if (fa[x]==x) return x; return fa[x]=find(fa[x]); } bool cmp(data a,data b){ return a.z<b.z; } void cdq(int dep,int l,int r,int n,int m,ll ans){ rep(i,1,m){ data &c=a[dep][i],&c2=a[dep-1][i]; a[dep][i]=(data){c2.x,c2.y,dis[c2.id],0,c2.id}; pos[c.id]=i; } //当l=r，计算答案，直接赋值当前修改边。 if (l==r){ data &c=a[dep][pos[b[l].k]]; c.z=dis[c.id]=b[l].w; rep(i,1,n) fa[i]=i; sort(a[dep]+1,a[dep]+1+m,cmp); rep(i,1,m){ int x=find(a[dep][i].x),y=find(a[dep][i].y); if (x!=y) fa[x]=y,ans+=a[dep][i].z; } printf("%lld ",ans); return; } //删边，如果k=0，那么这是一条无用的边。 rep(i,l,r) a[dep][pos[b[i].k]].k=1; rep(i,1,n) fa[i]=i; sort(a[dep]+1,a[dep]+1+m,cmp); rep(i,1,m) if (a[dep][i].k==0){ int x=find(a[dep][i].x),y=find(a[dep][i].y); if (x!=y) fa[x]=y,a[dep][i].k=2; } //删点，找出必连边（k=3） rep(i,1,m) if (a[dep][i].k==1) a[dep][i].z=-inf; rep(i,1,n) fa[i]=i; sort(a[dep]+1,a[dep]+1+m,cmp); rep(i,1,m) if (a[dep][i].k!=0){ int x=find(a[dep][i].x),y=find(a[dep][i].y); if (x!=y) { fa[x]=y; if (a[dep][i].k!=1) a[dep][i].k=3; } } //重建，把必连边（k=3）取为答案，将两端点缩为一个点。 rep(i,1,n) fa[i]=i; rep(i,1,m) if (a[dep][i].k==3){ data &c=a[dep][i]; int x=find(c.x),y=find(c.y); if (x!=y) fa[x]=y, ans+=c.z; } int nn=0,nm=0; rep(i,1,n) p[i]=0; rep(i,1,n) if (!p[find(i)]) p[find(i)]=++nn; rep(i,1,m) if (a[dep][i].k!=0){ int x=find(a[dep][i].x),y=find(a[dep][i].y); data &c=a[dep][i]; if (x!=y) a[dep][++nm]=(data){p[x],p[y],c.z,c.k,c.id}; } int mid=(l+r)/2; cdq(dep+1,l,mid,nn,nm,ans); cdq(dep+1,mid+1,r,nn,nm,ans); } int main(){ n=read(); m=read(); Q=read(); int x,y; ll z; rep(i,1,m){ x=read(); y=read(); z=read(); a[0][i]=(data){x,y,z,0,i}; } rep(i,1,Q){ x=read(); y=read(); b[i]=(node){x,y,i}; } rep(i,1,m) dis[a[0][i].id]=a[0][i].z; cdq(1,1,Q,n,m,0); return 0; }