题意：
分析：
- 暴力：
对于每一个操作，找出它加上或删掉影响的部分中最小的那个值，跟它比较之后决定删除或保留，复杂度 (O(qm))
- 正解：
我还在想分成树边和非树边分开考虑怎么计算时，巨佬一眼就切了
没错，就是线段树分治，因为每一条边被修改中之后等价于删掉这条旧的边，同时加入一条边权为修改的值的新边，这样转换之后相当于 (q+m) 条边，每一条都有一个存在的时间段，按照时间进行分治处理就可以了，同时我们需要一个数据结构支持动态加入和删除边，那么上 (LCT)
这个题相当于用 (LCT) 动态维护 (MST) ,和 魔法森林 那道题很像，需要转化一下用到一个小 (trick) ，就是说由于 (LCT) 是维护点权的数据结构，没有办法维护边权，所以我们需要新建一个节点来表示边，对于 (x o y) 这条边我们新建一个节点 (z) ，分别连接 (x) 和 (y) 它的点权等价于原来的边权，这个操作和重构树很类似
之后我们就按照正常方式进行线段树分治，同时 (lct) 每一个点维护区间点权最大的点的编号和值，这样我们就能 (log) 的查询出区间最大的边的位置，总体复杂度就是 (O(nlog ^2)) 但是由于 (LCT) 的复杂度极大，所以在这个题不主动进行卡常优化或吸氧是过不去的
- 另解：
由于上面提到的 线段树分治 + (LCT) 的做法不是很优，所以这里提供一个更优秀的做法，复杂度仅有 (O(nlog)) 的 (CDQ) 分治
想法就是，把每一次查询中重复的边我们称之为静态边，就是指那些不会被本次修改的边影响到的边，而会被本次操作影响到的边称之为动态边，而 (CDQ) 分治的过程就是一个不断将动态转化为静态的过程，这样我们按照时间偏序的关系不断递归分治下去，动态边会不断转化为静态边，直到形成一个静态的 (Kruskal)
栗子：
对于我们正在处理的 ((l,r)) 这段区间，将它分成 ((l,mid)(mid+1,r)) 两部分
当我们递归到 ((l,mid)) 时在 ((mid+1,r)) 中的动态边就转化成了静态边
然后我们用并查集维护静态边集，这样可知动态边集的大小随分治层数变化而变化
所以复杂度就是 (O(nlog^2))
我们需要可撤销并查集来动态维护静态边集
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fir first
#define sec second
#define mk(x,y) make_pair(x,y)
#define pb push_back
using namespace std;
namespace zzc
{
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 2e6+5;
int n,m,qt,cnt;
long long ans[maxn],sum;
int pos[maxn],lst[maxn];
vector<int> t[maxn];
namespace lct
{
int ch[maxn][2],top,q[maxn],fa[maxn],rev[maxn],siz[maxn],val[maxn],mx[maxn];
void pushup(int x)
{
mx[x]=x;
if(ch[x][0]&&val[mx[ch[x][0]]]>val[mx[x]])mx[x]=mx[ch[x][0]];
if(ch[x][1]&&val[mx[ch[x][1]]]>val[mx[x]])mx[x]=mx[ch[x][1]];
}
void pushdown(int x){int l=ch[x][0],r=ch[x][1];if(rev[x]){swap(ch[x][0],ch[x][1]);rev[l]^=1;rev[r]^=1;rev[x]=0;}}
bool isroot(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rotate(int x)
{
int y=fa[x],z=fa[y],l,r;
if(ch[y][0]==x)l=0;else l=1;r=l^1;
if(!isroot(y)){if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
fa[x]=z;fa[y]=x;fa[ch[x][r]]=y;
ch[y][l]=ch[x][r];ch[x][r]=y;
pushup(x);pushup(y);
}
void splay(int x)
{
q[top=1]=x;
for(int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i];
for(int i=top;i;i--) pushdown(q[i]);
while(!isroot(x))
{
int y=fa[x],z=fa[y];
if(!isroot(y))
{
if((ch[z][0]==y)^(ch[y][0]==x)) rotate(x);
else rotate(y);
}
rotate(x);
}
pushup(x);
}
void access(int x){for(int t=0;x;t=x,x=fa[x]){splay(x),ch[x][1]=t,pushup(x);}}
void makeroot(int x){access(x);splay(x);rev[x]=1;}
int findroot(int x){access(x);splay(x);while(ch[x][0])x=ch[x][0];return x;}
void split(int x,int y){makeroot(x);access(y);splay(y);}
void link(int x,int y){makeroot(x);fa[x]=y;}
void cut(int x,int y){split(x,y);if(ch[y][0]==x&&ch[x][1]==0)ch[y][0]=0,fa[x]=0,pushup(y);}
int query(int x,int y){split(x,y);return mx[y];}
}
using namespace lct;
struct edge
{
int frm,to,val;
edge(){}
edge(int frm,int to,int val):frm(frm),to(to),val(val){}
}e[maxn];
void modify(int rt,int l,int r,int ql,int qr,int id)
{
if(ql>qr) return ;
if(ql<=l&&r<=qr){t[rt].pb(id);return ;}
int mid=(l+r)>>1;
if(ql<=mid) modify(rt<<1,l,mid,ql,qr,id);
if(qr>mid) modify(rt<<1|1,mid+1,r,ql,qr,id);
}
int tot,st[maxn],flag[maxn];
void query(int rt,int l,int r)
{
int mid=(l+r)>>1,old=tot;
for(auto i:t[rt])
{
int frm=e[i].frm,to=e[i].to,w=e[i].val;
if(findroot(frm)==findroot(to))
{
int max_id=query(frm,to);
if(val[max_id]>w)
{
cut(e[max_id-n].frm,max_id);
cut(e[max_id-n].to,max_id);
sum-=e[max_id-n].val;
st[++tot]=max_id-n;
flag[tot]=1;
}
else continue;
}
link(i+n,frm);link(i+n,to);sum+=w;
st[++tot]=i;flag[tot]=-1;
}
if(l==r) ans[l]=sum;
else query(rt<<1,l,mid),query(rt<<1|1,mid+1,r);
for(int i=tot;i>old;i--)
{
if(flag[i]<0)
{
cut(st[i]+n,e[st[i]].frm);
cut(st[i]+n,e[st[i]].to);
sum-=e[st[i]].val;
}
else
{
link(st[i]+n,e[st[i]].frm);
link(st[i]+n,e[st[i]].to);
sum+=e[st[i]].val;
}
}
tot=old;
}
void work()
{
int k,d,x;
n=read();m=read();qt=read();cnt=m;
for(int i=1;i<=m;i++) pos[i]=i;
for(int i=1;i<=m;i++) e[i].frm=read(),e[i].to=read(),e[i].val=read(),lst[i]=1;
for(int i=1;i<=qt;i++)
{
k=read();d=read();x=pos[k];
modify(1,1,qt,lst[k],i-1,x);lst[k]=i;
e[++cnt]=e[x];e[cnt].val=d;pos[k]=cnt;
}
for(int i=1;i<=cnt;i++) val[i+n]=e[i].val;
for(int i=1;i<=m;i++) modify(1,1,qt,lst[i],qt,pos[i]);
query(1,1,qt);
for(int i=1;i<=qt;i++) printf("%lld
",ans[i]);
}
}
int main()
{
zzc::work();
return 0;
}