40pts求助

#include<bits/stdc++.h>

#define int long long

using namespace std;

int n,m,q;

const int N=2e4+5,M=5e4+5;

struct Edge{int u,v,val;}e[M];

template<const int SIZ>
struct DSU{
	int fa[SIZ],siz[SIZ],top=0;
	struct Opt{int u,v,su,sv;};
	Opt stk[SIZ];
	void Init(){for(int i=1;i<=n;i++) fa[i]=i,siz[i]=1;}
	int Find(int x){return fa[x]==x?x:Find(fa[x]);};
	bool Merge(int x,int y){
		int X=Find(x),Y=Find(y);
		if(X==Y) return false;
		if(siz[X]>siz[Y]) swap(X,Y);
		stk[++top]=(Opt){X,Y,siz[X],siz[Y]};
		fa[X]=Y,siz[Y]+=siz[X];
		return true;
	}
	void Remove(){
		int u=stk[top].u,v=stk[top].v,su=stk[top].su,sv=stk[top].sv;top--;
		fa[u]=u,fa[v]=v;
		siz[u]=su,siz[v]=sv;
	}
	void Clear(int x){while(top>x) Remove();};
};

DSU<N> dsu;

vector<int> sta,mov;//static edge and movable edge

int id[M],val[M];

int res,ans[N];

bool vis[M];//if the edge is static

bool cmp(int x,int y){return e[x].val<e[y].val;}

void Solve(int l,int r){
	int RES=res,SIZ=dsu.top;vector<int> STA=sta,MOV=mov;//old information
	
	vector<int> tmp;
	for(int i=l;i<=r;i++) vis[id[i]]=true;
	for(auto i:mov){
		if(vis[i]) tmp.push_back(i);
		else sta.push_back(i);
	}
	for(int i=l;i<=r;i++) vis[id[i]]=false;
	mov=tmp;
	
	tmp.clear();vector<int> mst;
	for(auto i:mov) dsu.Merge(e[i].u,e[i].v);
	sort(sta.begin(),sta.end(),cmp);
	for(auto i:sta){
		if(dsu.Merge(e[i].u,e[i].v)) res+=e[i].val,mst.push_back(i);
		else tmp.push_back(i);
	}
	sta=tmp,dsu.Clear(SIZ);
	for(auto i:mst) dsu.Merge(e[i].u,e[i].v);
	
	tmp.clear();int now=dsu.top;
	for(auto i:sta) if(dsu.Merge(e[i].u,e[i].v)) tmp.push_back(i);
	dsu.Clear(now);sta=tmp;
	
	if(l==r){
		e[id[l]].val=val[l],sta.push_back(id[l]);
		sort(sta.begin(),sta.end(),cmp);
		for(auto i:sta) if(dsu.Merge(e[i].u,e[i].v)) res+=e[i].val;
		ans[l]=res;
	}
	else{
		int mid=l+r>>1;
		Solve(l,mid),Solve(mid+1,r);
	}
	
	dsu.Clear(SIZ);
	res=RES,sta=STA,mov=MOV;
}

signed main()
{
	freopen("Burf.in","r",stdin);
	freopen("Burf.out","w",stdout);
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].val),mov.push_back(i);
	for(int i=1;i<=q;i++) scanf("%lld%lld",&id[i],&val[i]);
	dsu.Init();Solve(1,q);
	for(int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}