大致题意： 动态(MST)。每次修改一条边的边权，询问此时最小生成树。
前言
数数我犯的(SB)错误吧：
- 数组开小。（而且是两次！）
- 对(vis)数组使用了时间戳，然后使用时依然判断(!vis)。。。
(CDQ)分治
这道题居然是(CDQ)分治。。。我觉得我学的是假的(CDQ)。。。
据某大佬所言，(CDQ)分治的本质就是最大化各个询问间的重复操作，并将它们一并处理掉。
对于这道题，考虑我们分治操作区间。
则在这段操作区间内，必然有一部分边始终不被修改，一部分边会被修改。
而我们考虑，始终不被修改的边，递归到子区间里，依然是始终不被修改的。因此，我们就可以把这些边一起处理掉。
即，我们先把会被修改的边边权设为(-INF)，然后跑一遍最小生成树，此时被连在最小生成树上的不会被修改的边，显然在处理子区间时也能够被连在最小生成树上。因此，我们可以直接连上这条边。
然后，我们把会被修改的边边权设为(INF)，然后再跑一遍最小生成树，此时没有被连在最小生成树上的不会被修改的边，显然在处理子区间时也没有任何贡献。因此，我们可以直接删去这条边。
而剩下的边，就是可能有用的边，我们继续递归到子区间处理。
我觉得这一过程虽然自己比较难想出来，但理解应该还是不成问题的，所以就不多加解释了。
一个小细节
考虑我们要做很多次最小生成树，如果暴开一大堆并查集，就算不(TLE)也要(MLE)。因此，我们可以使用按秩合并的可撤销并查集。
具体实现可见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 20000
#define M 50000
#define Q 50000
#define LQ 18
#define LL long long
#define pb push_back
#define INF 1e9
#define swap(x,y) (x^=y^=x^=y)
using namespace std;
int n,m,q,key;struct Op {int x,v;}p[Q+5];
struct edge
{
int x,y,v,ty;
I friend bool operator < (Con edge& x,Con edge& y)//用于排序
{
return ((x.ty||!key)?x.v:key*INF)<((y.ty||!key)?y.v:key*INF);//key表示当前把会被修改的边权看作什么
}
}e[M+5];
I bool cmp(CI x,CI y) {return e[x]<e[y];}
class FastIO
{
private:
#define FS 100000
#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
#define pc(c) (C==E&&(clear(),0),*C++=c)
#define tn (x<<3)+(x<<1)
#define D isdigit(c=tc())
int T;char c,*A,*B,*C,*E,FI[FS],FO[FS],S[FS];
public:
I FastIO() {A=B=FI,C=FO,E=FO+FS;}
Tp I void read(Ty& x) {x=0;W(!D);W(x=tn+(c&15),D);}
Tp I void write(Ty x) {W(S[++T]=x%10+48,x/=10);W(T) pc(S[T--]);}
Tp I void writeln(Con Ty& x) {write(x),pc('
');}
I void clear() {fwrite(FO,1,C-FO,stdout),C=FO;}
}F;
class UnionFindSet//按秩合并并查集
{
private:
int T,f[N+5],g[N+5],Sx[N+5],Sy[N+5],Sf[N+5];
I int getfa(CI x) {return f[x]?getfa(f[x]):x;}//暴力找祖先
public:
I bool Id(CI x,CI y) {return getfa(x)==getfa(y);}//判断是否联通
I void Un(CI x,CI y)//合并
{
Sx[++T]=getfa(x),Sy[T]=getfa(y),g[Sx[T]]<g[Sy[T]]&&swap(Sx[T],Sy[T]),//按秩合并
f[Sy[T]]=Sx[T],g[Sx[T]]+=(Sf[T]=g[Sx[T]]==g[Sy[T]]);//用栈记下操作
}
I void Back() {f[Sy[T]]=0,g[Sx[T]]-=Sf[T],--T;}//撤销
}U;
class CDQSolver//CDQ分治
{
private:
LL ans[Q+5];int vis[M+5];vector<int> V[LQ+5];
I void Work(CI l,CI r,CI d,LL v)//处理[l,r]的修改
{
#define E e[V[d][i]]
RI i,sz=V[d].size(),t=0;if(l==r)//对于只有一个修改
{
e[p[l].x].v=p[l].v,key=0,sort(V[d].begin(),V[d].end(),cmp);//修改，然后sort
for(i=0;i^sz;++i) !U.Id(E.x,E.y)&&(U.Un(E.x,E.y),++t,v+=E.v);//MST
ans[l]=v;W(t) U.Back(),--t;return;//存储答案，撤销并查集
}
static int ti=0;++ti;for(i=l;i<=r;++i) vis[p[i].x]=ti;//标记会被修改的边权
for(i=0;i^sz;++i) E.ty=vis[V[d][i]]!=ti;//判断每条边的类型
for(key=-1,sort(V[d].begin(),V[d].end(),cmp),i=0;i^sz;++i)//找出可以直接连的边
!U.Id(E.x,E.y)&&(U.Un(E.x,E.y),++t,E.ty&&(E.ty=-1,v+=E.v));W(t) U.Back(),--t;
for(key=1,sort(V[d].begin(),V[d].end(),cmp),i=0;i^sz;++i)//找出肯定用不上的边
U.Id(E.x,E.y)?E.ty&&(E.ty=-2):(U.Un(E.x,E.y),++t);W(t) U.Back(),--t;
for(V[d+1].clear(),i=0;i^sz;++i)//连上可以直接连的边
!~E.ty&&(U.Un(E.x,E.y),++t),E.ty>=0&&(V[d+1].pb(V[d][i]),0);
int mid=l+r>>1;Work(l,mid,d+1,v),Work(mid+1,r,d+1,v);W(t) U.Back(),--t;//递归处理子区间
}
public:
I void Solve()
{
RI i;for(i=1;i<=m;++i) V[0].pb(i);//初始化vector
for(Work(1,q,0,0),i=1;i<=q;++i) F.writeln(ans[i]);//输出答案
}
}CDQ;
int main()
{
RI i;F.read(n),F.read(m),F.read(q);
for(i=1;i<=m;++i) F.read(e[i].x),F.read(e[i].y),F.read(e[i].v);
for(i=1;i<=q;++i) F.read(p[i].x),F.read(p[i].v);
return CDQ.Solve(),F.clear(),0;
}