Description

PS国是一个拥有诸多城市的大国，国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变，Louis会不断得到某道路的修建代价改变的消息，他希望每得到一条消息后能立即知道使城市连通的最小花费总和， Louis决定求助于你来完成这个任务。

Input

文件第一行包含三个整数N,M,Q，分别表示城市的数目，可以修建的道路个数，及收到的消息个数。 接下来M行，第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000)，表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行，每行包含两个数k,d，表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。

Output

输出包含Q行，第i行输出得知前i条消息后使城市连通的最小花费总和。

Sample Input

5 5 3

1 2 1

2 3 2

3 4 3

4 5 4

5 1 5

1 6

1 1

5 3

Sample Output

14

10

9

HINT

【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据，n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。

Solution

注意：下面的程序并不能AC此题，因为常数卡不过了

比较喜欢LCT，所以直接想到LCT上去了，正解其实并不是这样

类似于【刷题】洛谷 P4319 变化的道路用时间线段树分治用LCT维护MST

思路贼简单，但是常数太大了啊！！！！

复杂度是正确的，\(log\) 方的，但常数大到根本卡不过

读者就当看一看吧，如果你没有wys的卡常技巧，就千万不要这样写

#include<bits/stdc++.h>

#define ui unsigned int

#define ll long long

#define db double

#define ld long double

#define ull unsigned long long

const int MAXN=20000+10,MAXM=50000+10,MAXP=120000+10;

int n,m,q;

ll ans;

struct pair{

	int first,second;

};

pair las[MAXM];

struct node{

	int u,v,w;

};

node side[MAXM<<1];

#define lc(x) ch[(x)][0]

#define rc(x) ch[(x)][1]

struct LinkCut_Tree{

	int ch[MAXP][2],fa[MAXP],rev[MAXP],Mx[MAXP],id[MAXP],cnt,stack[MAXP],val[MAXP];

	inline bool nroot(int x)

	{

		return lc(fa[x])==x||rc(fa[x])==x;

	}

	inline void reverse(int x)

	{

		std::swap(lc(x),rc(x));

		rev[x]^=1;

	}

	inline void pushup(int x)

	{

		Mx[x]=val[x],id[x]=x;

		if(Mx[lc(x)]>Mx[x])Mx[x]=Mx[lc(x)],id[x]=id[lc(x)];

		if(Mx[rc(x)]>Mx[x])Mx[x]=Mx[rc(x)],id[x]=id[rc(x)];

	}

	inline void pushdown(int x)

	{

		if(rev[x])

		{

			if(lc(x))reverse(lc(x));

			if(rc(x))reverse(rc(x));

			rev[x]=0;

		}

	}

	inline void rotate(int x)

	{

		int f=fa[x],p=fa[f],c=(rc(f)==x);

		if(nroot(f))ch[p][rc(p)==f]=x;

		fa[ch[f][c]=ch[x][c^1]]=f;

		fa[ch[x][c^1]=f]=x;

		fa[x]=p;

		pushup(f);

		pushup(x);

	}

	inline void splay(int x)

	{

		cnt=0;

		stack[++cnt]=x;

		for(register int i=x;nroot(i);i=fa[i])stack[++cnt]=fa[i];

		while(cnt)pushdown(stack[cnt--]);

		for(register int y=fa[x];nroot(x);rotate(x),y=fa[x])

			if(nroot(y))rotate((lc(y)==x)==(lc(fa[y])==y)?y:x);

		pushup(x);

	}

	inline void access(int x)

	{

		for(register int y=0;x;x=fa[y=x])splay(x),rc(x)=y,pushup(x);

	}

	inline void makeroot(int x)

	{

		access(x);splay(x);reverse(x);

	}

	inline int findroot(int x)

	{

		access(x);splay(x);

		while(lc(x))pushdown(x),x=lc(x);

		splay(x);

		return x;

	}

	inline void split(int x,int y)

	{

		makeroot(x);access(y);splay(y);

	}

	inline void link(int x,int y)

	{

		makeroot(x);fa[x]=y;

	}

	inline void cut(int x,int y)

	{

		split(x,y);fa[x]=lc(y)=0;pushup(y);

	}

};

LinkCut_Tree T1;

#undef lc

#undef rc

template<typename T> inline void read(T &x)

{

	T data=0,w=1;

	char ch=0;

	while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();

	if(ch=='-')w=-1,ch=getchar();

	while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();

	x=data*w;

}

template<typename T> inline void write(T x,char ch='\0')

{

	if(x<0)putchar('-'),x=-x;

	if(x>9)write(x/10);

	putchar(x%10+'0');

	if(ch!='\0')putchar(ch);

}

template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}

template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}

template<typename T> inline T min(T x,T y){return x<y?x:y;}

template<typename T> inline T max(T x,T y){return x>y?x:y;}

#define ft first

#define sd second

#define Mid ((l+r)>>1)

#define ls rt<<1

#define rs rt<<1|1

#define lson ls,l,Mid

#define rson rs,Mid+1,r

struct Segment_Tree{

	std::vector<int> V[MAXM<<2];

	inline void Update(int rt,int l,int r,int L,int R,int k)

	{

		if(L<=l&&r<=R)V[rt].push_back(k);

		else

		{

			if(L<=Mid)Update(lson,L,R,k);

			if(R>Mid)Update(rson,L,R,k);

		}

	}

	inline void Query(int rt,int l,int r)

	{

		std::stack<pair> S;

		for(register int i=0,lt=V[rt].size();i<lt;++i)

		{

			int u=side[V[rt][i]].u,v=side[V[rt][i]].v,w=side[V[rt][i]].w,sn=V[rt][i]+n;

			if(u==v)continue;

			T1.makeroot(u);

			if(T1.findroot(v)!=u)

			{

				ans+=w,T1.val[sn]=w;

				T1.link(sn,u);T1.link(sn,v);

				S.push((pair){sn,0});

			}

			else

			{

				T1.split(u,v);

				if(w<T1.Mx[v])

				{

					ans-=T1.Mx[v]-w;

					int so=T1.id[v];

					T1.cut(so,side[so-n].u);T1.cut(so,side[so-n].v);

					S.push((pair){so,1});

					T1.val[sn]=w;

					T1.link(sn,u);T1.link(sn,v);

					S.push((pair){sn,0});

				}

			}

		}

		if(l==r)printf("%lld\n",ans);

		else Query(lson),Query(rson);

		while(!S.empty())

		{

			pair pr=S.top();

			S.pop();

			int sn=pr.ft;

			if(!pr.sd)T1.cut(side[sn-n].u,sn),T1.cut(side[sn-n].v,sn),ans-=side[sn-n].w;

			else T1.link(side[sn-n].u,sn),T1.link(side[sn-n].v,sn),ans+=side[sn-n].w;

		}

	}

};

Segment_Tree T2;

#undef Mid

#undef ls

#undef rs

#undef lson

#undef rson

int main()

{

	read(n);read(m);read(q);

	static int om=m;

	for(register int i=1;i<=m;++i)

	{

		int u,v,w;read(u);read(v);read(w);

		side[i]=(node){u,v,w};las[i]=(pair){0,i};

	}

	for(register int i=1;i<=q;++i)

	{

		int k,d;read(k);read(d);

		side[++m]=(node){side[k].u,side[k].v,d};

		if(i-1>las[k].ft)T2.Update(1,1,q,las[k].ft+1,i-1,las[k].sd);

		las[k]=(pair){i-1,m};

	}

	for(register int i=1;i<=om;++i)

		if(las[i].ft^q)T2.Update(1,1,q,las[i].ft+1,q,las[i].sd);

	T2.Query(1,1,q);

	return 0;

}