记录编号	155731	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1754.[HNOI 2010]城市建设	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	3.463 s
提交时间	2015-03-30 08:26:23	内存使用	17.76 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 20100;
const int M = 50100;
const int Q = 50100;
const int MAXD = 20; 
const int INF = 0x3f3f3f3f;
typedef long long LL;
int n,m,q;
struct Edge{
	int x,y,w,id;
	bool operator < (const Edge &a) const{if(w<a.w) return 1;return 0;}
}G[MAXD][M],ax[M];
int id[Q],val[Q],ori[M],f[N],ref[M],cho[M];
LL Ans[Q];

int Find(int x){if(f[x]==x) return x;return f[x]=Find(f[x]);}
void Reset(int m){for(int i=1;i<=m;i++) f[ax[i].x]=ax[i].x,f[ax[i].y]=ax[i].y;return;}

void Solve(int dep,int l,int r,int m,LL res){
	if(l>r) return;
	if(l==r) ori[id[l]]=val[l];
	for(int i=1;i<=m;i++) G[dep][i].w=ori[G[dep][i].id],ax[i]=G[dep][i];
	for(int i=1;i<=m;i++) ref[ax[i].id]=i;
	Reset(m);
	if(l==r){
		sort(ax+1,ax+m+1);
		for(int fx,fy,i=1;i<=m;i++){
			fx=Find(ax[i].x),fy=Find(ax[i].y);
			if(fx==fy) continue;
			f[fy]=fx;res+=ax[i].w;
		}
		Ans[l]=res;
		return;
	}
	int mm=0,mid=(l+r)>>1;
	for(int i=l;i<=r;i++) ax[ref[id[i]]].w=-INF;//contraction
	sort(ax+1,ax+m+1);
	cho[0]=0;
	for(int fx,fy,i=1;i<=m;i++){
		fx=Find(ax[i].x),fy=Find(ax[i].y);
		if(fx==fy) continue;
		f[fy]=fx;cho[++cho[0]]=i;
	}
	Reset(m);
	for(int p,fx,fy,i=1;i<=cho[0];i++){
		p=cho[i];
		if(ax[p].w!=-INF){ 
			fx=Find(ax[p].x),fy=Find(ax[p].y);
			if(fx!=fy) f[fy]=fx;
			res+=ax[p].w;
		}
	}
	for(int i=1;i<=m;i++){
		ax[i].x=Find(ax[i].x),ax[i].y=Find(ax[i].y);
		if(ax[i].w==-INF) ax[i].w=INF;
	}
	sort(ax+1,ax+m+1);
	for(int fx,fy,i=1;i<=m;i++){
		fx=Find(ax[i].x),fy=Find(ax[i].y);
		if(fx==fy) continue;
		f[fy]=fx;
		if(ax[i].w!=INF) G[dep+1][++mm]=ax[i];
	}
	for(int i=1;i<=m;i++) if(ax[i].w==INF) G[dep+1][++mm]=ax[i];
	Solve(dep+1,l,mid,mm,res);Solve(dep+1,mid+1,r,mm,res);
	return;
}

int main(){
	#define test
	#ifdef test
		freopen("hnoi2010_city.in","r",stdin);
		freopen("hnoi2010_city.out","w",stdout);
	#endif
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&G[0][i].x,&G[0][i].y,&G[0][i].w);
		ori[i]=G[0][i].w;G[0][i].id=i;
	}
	for(int i=1;i<=q;i++) scanf("%d%d",&id[i],&val[i]);
	Solve(0,1,q,m,0);
	for(int i=1;i<=q;i++) printf("%lld\n",Ans[i]);
	return 0;
}