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

//抄了一遍 = = 还是良心地写点注释好了 人太虚 简直不能多说 
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 20001;
const int M = 50001;
const int Q = 50001;
const int MaxD = 20;
const int inf = 0x3fffffff;
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[Q],f[N],ref[M],cho[M];//前两个是修改的编号和值 ori代表到当前为止每条边对应的值 f是并查集 ref是边的映射 cho是个辅助数组之后用到 
LL Ans[Q];//答案数组 

int Find(int x){if(f[x]==x) return f[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];//修改到l了 直接改掉就好了  
	for(int i=1;i<=m;i++) G[dep][i].w=ori[G[dep][i].id],ax[i]=G[dep][i]; //copy一下 虽然dep的G没什么用= = 
	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;//contraction 选出必选边 
	for(int i=l;i<=r;i++) ax[ref[id[i]]].w=-inf;//把有修改的赋成-inf 筛出必选的 
	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) continue;
		fx=Find(ax[p].x),fy=Find(ax[p].y);//不是-inf一定会在之后被选中 选选选 统计对答案的贡献后 把他缩成一个点 之后就用不到了 
		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);//reduction 筛选出必不选的边  
	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];//不是inf会被选中的扔到下张图去 
	}
	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);//balbala 
	return;
}
//END
int main(){
	#define READ
	#ifdef READ
		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;
}