PS 国是一个拥有诸多城市的大国。国王 Louis 为城市的交通建设可谓绞尽脑汁。Louis 可以在某些城市之间修建道路，在不同的城市之间修建道路需要不同的花费。
Louis 希望建造最少的道路使得国内所有的城市连通。但是由于某些因素，城市之间修建道路需要的花费会随着时间而改变。Louis 会不断得到某道路的修建代价改变的消息。他希望每得到一条消息后能立即知道使城市连通的最小花费总和。Louis 决定求助于你来完成这个任务。
\(1\le n\le 2\times 10^4\)，\(1\le m,q\le 5\times 10^4\)，\(1\le x_i,y_i\le n\)，\(0\le z_i\le 5\times 10^7\)。
奇妙题。
首先有一个显然的 LCT 做法：加边的时候，可以用 LCT 求出链上的最小值，删边用线段树分治改为撤销就可以了。理论复杂度 \(O(qlog^2n)\)，常数超大，但是过得去，不过跑不了 \(10^5\)（应该吧）
这里有一个更加巧妙的分治做法。仍然是线段树分治，但是当分治到一个区间 \([l,r]\) 的时候，有一些边是在这个分治区间不会改变的称为静态边。有一些边是在这个区间有改变过的，成为动态边。动态边最多有 \(r-l\) 个。
静态边的数量过多，我们尝试减少点。先强制把所有动态边加上，此时如果还需要加上的静态边在区间中最后一定会被加上，可以在分治到这里的时候就加上。而强制把所有动态边删去，此时如果不需要加上的静态边在未来也一定不会被加上，可以删去，不再递归到后面的区间。而这个过程可以用可撤销并查集维护。
这样子的复杂度是 \(O(nlog^2n)\)。来证明一下。将所有加入动态边加入后再加上的静态边永久的加入并查集，而此时剩下的点就是动态边加入的点，所以有 \(O(r-l)\) 个。而只加入静态边时没被加入的永久不加入，这说明下传下去的边最多有 \(O(r-l)\) 个。加上可撤销并查集，总复杂度 \(O(nlog^2n)\)
#include<bits/stdc++.h>
using namespace std;
const int N=8e4+5;
typedef long long LL;
int read()
{
int s=0;
char ch=getchar();
while(ch<'0'||ch>'9')
ch=getchar();
while(ch>='0'&&ch<='9')
s=s*10+ch-48,ch=getchar();
return s;
}
struct node{
int x,y,z;
bool operator<(const node&n)const{
return z<n.z;
}
}st[60*N];
int fa[N],n,m,q,sz[N],fr[N],tp;
LL ans,an[N];
int find(int x)
{
if(fa[x]==x)
return x;
return find(fa[x]);
}
int merge(int x,int y)//返回是否在一个连通块
{
int fx=find(x),fy=find(y);
if(fx==fy)
return 1;
if(sz[fx]>sz[fy])
swap(fx,fy);
st[++tp]=(node){fx,fy,0};
sz[fy]+=sz[fx],fa[fx]=fy;
return 0;
}
void del(int t)
{
while(tp^t)
{
int x=st[tp].x,y=st[tp].y;
sz[y]-=sz[x],fa[x]=x;
--tp;
}
}
vector<node>tr[N*4],p[N*4];//tr存动态边，p存静态边
void update(int o,int l,int r,int x,int y,node k)
{
if(x<=l&&r<=y)
{
p[o].push_back(k);
return;
}
tr[o].push_back(k);
int md=l+r>>1;
if(md>=x)
update(o<<1,l,md,x,y,k);
if(md<y)
update(o<<1|1,md+1,r,x,y,k);
}
void dfs(int o,int l,int r)
{
sort(p[o].begin(),p[o].end());
if(l==r)
{
LL ret=0;
int nw=tp;
for(int i=0;i<p[o].size();i++)
if(!merge(p[o][i].x,p[o][i].y))
ret+=p[o][i].z;
an[l]=ret+ans;
del(nw);
return;
}
int md=l+r>>1;
int nw=tp;
static int v[N];
LL ct=ans;
for(int i=0;i<tr[o].size();i++)
merge(tr[o][i].x,tr[o][i].y);
for(int i=0;i<p[o].size();i++)
{
v[i]=0;
if(!merge(p[o][i].x,p[o][i].y))
ans+=p[o][i].z,v[i]=1;
}
del(nw);
for(int i=0;i<p[o].size();i++)
{
if(v[i])
merge(p[o][i].x,p[o][i].y);
else if(!merge(p[o][i].x,p[o][i].y))
{
p[o<<1].push_back(p[o][i]);
p[o<<1|1].push_back(p[o][i]);
}
}
del(nw);
for(int i=0;i<p[o].size();i++)
if(v[i])
merge(p[o][i].x,p[o][i].y);
dfs(o<<1,l,md);
dfs(o<<1|1,md+1,r);
del(nw);
ans=ct;
}
int main()
{
n=read(),m=read(),q=read();
for(int i=1;i<=n;i++)
fa[i]=i,sz[i]=1;
static int u[N],v[N],w[N];
for(int i=1;i<=m;i++)
u[i]=read(),v[i]=read(),w[i]=read(),fr[i]=1;
for(int i=1;i<=q;i++)
{
int k=read(),d=read();
if(i^1)
update(1,1,q,fr[k],i-1,(node){u[k],v[k],w[k]});
w[k]=d,fr[k]=i;;
}
for(int i=1;i<=m;i++)
update(1,1,q,fr[i],q,(node){u[i],v[i],w[i]});
dfs(1,1,q);
for(int i=1;i<=q;i++)
printf("%lld\n",an[i]);
return 0;
}