记录编号	386057	评测结果	AAAAAAAAAAAAAAAATTTA
题目名称	[HNOI 2010]城市建设	最终得分	85
用户昵称	liaoy	是否通过	未通过
代码语言	C++	运行时间	10.909 s
提交时间	2017-03-23 11:46:26	内存使用	9.27 MiB

#include<cstdio>
#include<vector>
using namespace std;
char ch;
inline void read(int &a){
	for(ch=getchar();ch>'9'||ch<'0';ch=getchar());
	for(a=0;ch<='9'&&ch>='0';ch=getchar())(a*=10)+=ch-'0';
}
int n,m,q;
struct rec{
	int u,v,num,w;
}E[50010];
int L[50010],R[50010];
struct node{
	vector<rec> E;
	int m,l,r;
}Seg[50010<<2];
void Segbuild(const int &p,const int &l,const int &r){
	Seg[p].l=l; Seg[p].r=r; Seg[p].m=(l+r)>>1; if(l==r)return;
	Segbuild(p<<1,l,Seg[p].m); Segbuild(p<<1|1,Seg[p].m+1,r);
}
void put(const int &p,const rec &x,const int &l,const int &r){
	if(Seg[p].l==l&&Seg[p].r==r){
		Seg[p].E.push_back(x);
		return;
	}
	if(r<=Seg[p].m)put(p<<1,x,l,r);
	else
	if(Seg[p].m+1<=l)put(p<<1|1,x,l,r);
	else
	put(p<<1,x,l,Seg[p].m),put(p<<1|1,x,Seg[p].m+1,r);
}
long long sum;
struct LCT{
	struct node{
		int u;
		int s[2],data,maxp;
		bool inv;
		bool operator <(const node &x)const{
			return data<x.data;
		}
	}Btr[70010];
	int Fa[70010];
	int f,gf,v,s;
	inline void newdata(const int &p,const int &w){
		Btr[p].data=w; Btr[p].maxp=p;
	}
	void unite(const int &p){
		Btr[p].maxp=Btr[Btr[Btr[p].s[0]].maxp]<Btr[Btr[Btr[p].s[1]].maxp]?Btr[Btr[p].s[1]].maxp:Btr[Btr[p].s[0]].maxp;
		if(Btr[Btr[p].maxp]<Btr[p])Btr[p].maxp=p;
	}
	inline void flip(const int &p){
		if(Btr[p].inv){
			swap(Btr[p].s[0],Btr[p].s[1]);
			Btr[Btr[p].s[0]].inv^=1; Btr[Btr[p].s[1]].inv^=1; Btr[p].inv^=1;
		}
	}
	void rot(const int &p){
		f=Fa[p]; gf=Fa[f]; v=Btr[f].s[0]!=p;
		s=Btr[p].s[v^1]; Btr[p].s[v^1]=f; Btr[f].s[v]=s; Fa[s]=f; Fa[p]=gf; Fa[f]=p; unite(f); unite(p);
		if(gf){if(Btr[gf].s[0]==f)Btr[gf].s[0]=p;else if(Btr[gf].s[1]==f)Btr[gf].s[1]=p;}
	}
	inline bool Beroot(const int &p){
		return Btr[Fa[p]].s[0]!=p&&Btr[Fa[p]].s[1]!=p;
	}
	int stk[70010]; int stktop;
	void Splay(const int &p){
		for(v=p;!Beroot(v);v=Fa[v])stk[++stktop]=v; stk[++stktop]=v;
		while(stktop)flip(stk[stktop--]);
		for(;!Beroot(Fa[p])&&!Beroot(p);rot(p)){
			if((Btr[Fa[Fa[p]]].s[0]!=Fa[p])^(Btr[Fa[p]].s[0]!=p))rot(p);else rot(Fa[p]);
		}
		if(!Beroot(p))rot(p);
	}
	int t;
	void Access(int p){
		for(t=0;p;t=p,p=Fa[p]){
			Splay(p); Btr[p].s[1]=t; unite(p);
		}
	}
	void Make_root(const int &x){
		Access(x); Splay(x); Btr[x].inv^=1;
	}
	void Link(const int &x,const int &y){
		sum+=Btr[x].data+Btr[y].data;
		Make_root(x); Fa[x]=y;
	}
	/*
	void Cut(const int &x,const int &y){
		sum-=Btr[x].data+Btr[y].data;
		Make_root(x); Access(y); Splay(x);
		Btr[x].s[1]=0; Fa[y]=0; unite(x);
	}
	*/
	void Cut(const int &x,const int &u,const int &v){
		sum-=Btr[x].data<<1;
		Make_root(x);
		Access(u); Splay(x); Btr[x].s[1]=0; Fa[u]=0; unite(x);
		Access(v); Splay(x); Btr[x].s[1]=0; Fa[v]=0; unite(x);
	}
	int Getfa(int x){
		Access(x); Splay(x);
		for(flip(x);Btr[x].s[0];flip(x))x=Btr[x].s[0];
		return x;
	}
	bool Query(int x,const int &y){
		return Getfa(x)==Getfa(y);
		/*
		Make_root(x); Access(y); Splay(x);
		for(flip(x);Btr[x].s[1];flip(x))x=Btr[x].s[1];
//		Splay(x);
		return x==y;
		*/
	}
}T;
int Fa[20010],Size[20010];
struct ope{
	int x,y;/*表示把x的fa变为了y*/
}D[50010];
int Getfa(int u){
	for(;u!=Fa[u];u=Fa[u]); return u;
}
void unite(const int &num,const int &u,const int &v){
	int fu=Getfa(u),fv=Getfa(v); if(fu==fv)return;
	if(Size[fu]>Size[fv])swap(fu,fv); Fa[fu]=fv; Size[fv]+=Size[fu]; D[num].x=fu; D[num].y=fv;
}
inline void cancel(const int &num){
	if(!D[num].x)return;
	Size[D[num].y]-=Size[D[num].x]; Fa[D[num].x]=D[num].x; D[num].x=D[num].y=0;
}
bool Query(const int &u,const int &v){
	return Getfa(u)==Getfa(v);
}
long long Ans[50010];
struct opt{
	int foru;
	/*
	O[i]表示E[i]这条边，切断了foru（LCT中的点）。
	特别的，如果foru为0表示没有切断（但还是插入了这条边），如果foru为-1表示没有操作或者操作失败 
	*/
}O[50010];
void SegDiv(const int &p,const int &l,const int &r){
	int vi,u,v,w,num,maxp;
	for(vi=0;vi<Seg[p].E.size();vi++){
		u=Seg[p].E[vi].u; v=Seg[p].E[vi].v; w=Seg[p].E[vi].w; num=Seg[p].E[vi].num;
		if(!Query(u,v)){
			T.newdata(num+n,w);/*important*/
			T.Link(num+n,u); T.Link(num+n,v); unite(num,u,v);
			O[num].foru=0;
		}else{
			T.Make_root(u); T.Access(v); T.Splay(u);
			maxp=T.Btr[u].maxp;
			if(T.Btr[maxp].data<=w)continue;
			T.newdata(num+n,w);/*important*/
			O[num].foru=maxp;
			T.Cut(maxp,E[maxp-n].u,E[maxp-n].v);T.Link(num+n,u); T.Link(num+n,v);
		}
	}
	if(l!=r){
		SegDiv(p<<1,l,Seg[p].m); SegDiv(p<<1|1,Seg[p].m+1,r);	
	}else{
		Ans[l]=sum>>1;
	}
	for(vi=Seg[p].E.size()-1;vi>=0;vi--){
		num=Seg[p].E[vi].num;
		if(O[num].foru==-1)continue;else{
			T.Cut(num+n,E[num].u,E[num].v); cancel(num);
			if(O[num].foru){
				T.Link(O[num].foru,E[O[num].foru-n].u); T.Link(O[num].foru,E[O[num].foru-n].v);
			}
			O[num].foru=-1;
		}
	}
}
int main(){
	int i,k,w;
	freopen("hnoi2010_city.in","r",stdin); freopen("hnoi2010_city.out","w",stdout);
	read(n); read(m); read(q);
	for(i=1;i<=n;i++)Fa[i]=i,Size[i]=1;
	Segbuild(1,0,q);
	for(i=1;i<=m;i++)read(E[i].u),read(E[i].v),read(E[i].w),E[i].num=i,O[i].foru=-1;
	for(i=1;i<=q;i++){
		read(k); read(w); R[k]=i-1; put(1,E[k],L[k],R[k]); L[k]=i; E[k].w=w;
	}
	for(i=1;i<=m;i++)put(1,E[i],L[i],q);
	SegDiv(1,0,q);
	for(i=1;i<=q;i++)printf("%lld\n",Ans[i]);
}