Lvat_s Blog

这题是我当初学习CDQ分治时候的神级题目……当时不会做一直拖到现在

这题是动态维护最小生成树，但是是可以离线的，所以我们用CDQ分治对操作进行分治

每一层内用两个操作进行维护

$Contraction$:删除必定在最小生成树中的边并把贡献进行统计(不修改的情况下)

$Reduction$:删除必定不在最小生成树中的边(不修改的情况下)

这样到最后统计时边集的规模就已经相当小了，可以暴力Kruskal统计

但是边集是不断变化的很麻烦所以我们每层建一个边集就可以了

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=20005,M=50005,Lg2=22,INF=1000000000;

int n,m,q,siz[N],f[N],a[M],sum[M],c[M];
long long ans[M];

struct Edge{
int u,v,w,id;
inline friend bool operator<(const Edge &A,const Edge &B){return A.w<B.w;}
}e[Lg2][M],d[M],t[M];

struct Query{
int x,y;
}que[M];

inline void Clear(const int &cnt){for(register int i=1;i<=cnt;i++){f[d[i].u]=f[d[i].v]=0;siz[d[i].u]=siz[d[i].v]=1;}}
int Find(int x){return !f[x]?x:f[x]=Find(f[x]);}
inline void Merge(int x,int y){x=Find(x);y=Find(y);if(siz[x]>siz[y])f[y]=x,siz[x]+=siz[y];else f[x]=y,siz[y]+=siz[x];}

inline void Reduction(int &tot){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++){
    if(Find(d[i].u)!=Find(d[i].v)){
		Merge(d[i].u,d[i].v);
		d[++tp]=d[i];
		c[d[i].id]=tp;
    }
    else if(d[i].w==INF){
        d[++tp]=d[i];
        c[d[i].id]=tp;
    }
}
tot=tp;
}

inline void Contraction(int &tot,long long &val){
int tp=0;
Clear(tot);
sort(d+1,d+tot+1);
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){Merge(d[i].u,d[i].v);t[++tp]=d[i];}
for(register int i=1;i<=tp;i++)f[t[i].u]=f[t[i].v]=0,siz[t[i].u]=siz[t[i].v]=1;
for(register int i=1;i<=tp;i++)if(Find(t[i].u)!=Find(t[i].v) && t[i].w!=-INF){Merge(t[i].u,t[i].v);val+=t[i].w;}
tp=0;
for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v)){d[++tp]=d[i];c[d[i].id]=tp;d[tp].u=Find(d[tp].u);d[tp].v=Find(d[tp].v);}
tot=tp;
}

void CDQ(int l,int r,int now,long long val){
int tot=sum[now];
if(l==r)a[que[l].x]=que[l].y;
for(register int i=1;i<=tot;i++)e[now][i].w=a[e[now][i].id];
for(register int i=1;i<=tot;i++)d[i]=e[now][i],c[d[i].id]=i;
if(l==r){
	ans[l]=val;
    Clear(tot);
    sort(d+1,d+tot+1);
	for(register int i=1;i<=tot;i++)if(Find(d[i].u)!=Find(d[i].v))ans[l]+=d[i].w,Merge(d[i].u,d[i].v);
    return;
}
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=-INF;
Contraction(tot,val);
for(register int i=l;i<=r;i++)d[c[que[i].x]].w=INF;
Reduction(tot);
sum[now+1]=tot;
for(register int i=1;i<=tot;i++)e[now+1][i]=d[i];
int mid=l+r>>1;
CDQ(l,mid,now+1,val);CDQ(mid+1,r,now+1,val);
}

inline void Read(int &x){
static char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0';
}

int main(){
freopen("2001.in","r",stdin);
freopen("2001.out","w",stdout);
Read(n);Read(m);Read(q);sum[0]=m;
for(register int i=1;i<=m;i++)Read(e[0][i].u),Read(e[0][i].v),Read(a[i]),e[0][i].id=i,e[0][i].w=a[i];
for(register int i=1;i<=q;i++)Read(que[i].x),Read(que[i].y);
CDQ(1,q,0,0);
for(register int i=1;i<=q;i++)printf("%lld\n",ans[i]);
return 0;
}