记录编号	380434	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2010]城市建设	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.524 s
提交时间	2017-03-09 12:55:45	内存使用	8.51 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long ll;
const int N=2e5+10;
struct UFS{
	int fa[N];
	void init(int size){for (int i=1;i<=size;i++) fa[i]=i;}
	int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
}S;
int n,m,q,last[N];
struct edge{int u,v,l,L,R;}w[N];
bool cmp(const edge &x,const edge &y){return x.l<y.l;}
vector<edge> E;
ll ans[N];
bool cover[N],del[N],use[N];
int new_id[N];
void solve(int l,int r,int n,vector<edge> E){
	vector<edge> copy;
	//删掉不相交的边 
	for (int i=0;i<E.size();i++)
		if (l<=E[i].R&&r>=E[i].L) copy.push_back(E[i]);
	sort(copy.begin(),copy.end(),cmp);
	//求出一定会使用的边,use=1 
	S.init(n);
	ll sum=0;
	for (int i=0;i<copy.size();i++){
		edge x=copy[i];
		cover[i]=(x.L<=l&&x.R>=r);//标记覆盖[l,r]的边 
		del[i]=use[i]=0;
		int a=S.find(x.u),b=S.find(x.v);
		if (a!=b){
			S.fa[a]=b;
			if (cover[i]) sum+=x.l,use[i]=1;
		}
	}
	for (int i=l;i<=r;i++) ans[i]+=sum;
	if (l==r) return;
	//求出一定不会使用的边,del=1 
	S.init(n);
	for (int i=0;i<copy.size();i++){
		edge x=copy[i];
		int a=S.find(x.u),b=S.find(x.v);
		if (a==b) del[i]=1;else
		if (cover[i]) S.fa[a]=b;
	}
	//缩点,删边 
	S.init(n);
	for (int i=0;i<copy.size();i++)
	if (use[i]){
		edge x=copy[i];
		S.fa[S.find(x.u)]=S.find(x.v);
	}
	int cnt=0;
	for (int i=1;i<=n;i++)
		if (S.find(i)==i) new_id[i]=++cnt;
	E.clear();
	for (int i=0;i<copy.size();i++)
	if (!use[i]&&!del[i]){
		copy[i].u=new_id[S.find(copy[i].u)];
		copy[i].v=new_id[S.find(copy[i].v)];
		E.push_back(copy[i]);
	}
	copy.clear();
	int mid=(l+r)>>1;
	solve(l,mid,cnt,E);
	solve(mid+1,r,cnt,E);
}
int main()
{
	freopen("hnoi2010_city.in","r",stdin);
	freopen("hnoi2010_city.out","w",stdout);
	scanf("%d%d%d",&n,&m,&q);
	for (int i=1;i<=m;i++)
		scanf("%d%d%d",&w[i].u,&w[i].v,&w[i].l);
	for (int i=1;i<=q;i++){
		int id,v;
		scanf("%d%d",&id,&v);
		edge x=w[id];
		x.L=last[id];x.R=i-1;
		E.push_back(x);
		w[id].l=v;
		last[id]=i;
	}
	for (int i=1;i<=m;i++){
		w[i].L=last[i];w[i].R=q;
		E.push_back(w[i]);
	}
	solve(1,q,n,E);
	for (int i=1;i<=q;i++) printf("%lld\n",ans[i]);
	return 0;
}