大意：给你一棵树，每次永久修改一条边权，询问当前最小生成树
做法真的妙妙的
考虑到无论我们怎么修改某条边的边权
都总有一些边可以被选到
也总有一些边不会被选到
因此就引入了两个操作
我们将当前分治区间的所有要修改的边全部赋为
那么显然当前如果在中的边肯定会在中
那我们就可以把这些边缩成一个点来缩小图的规模
同理将这些边赋为
那么此时不在中的边肯定不会在内
那这些边我们就可以弃掉不要了
注意理解我们在分治的每一层都进行了这个操作
这样减少的点是逐渐递进的
而这样到最后的时候就已经只剩会影响的边了
便可以快速统计答案了
复杂度
#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read(){
char ch=getchar();
int res=0,f=1;
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch))res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
return res*f;
}
const int N=50005;
const int Log=20;
const ll inf=0x3f3f3f3f;
int m,n,k,ans[N],fa[N],num[Log],a[N],rk[N],p[N];
struct edge{
int u,v,val,pos;
}e[Log][N],q1[N],q2[N];
inline bool comp(const edge &a,const edge &b){
return a.val<b.val;
}
struct ask{
int pos,val;
ll ans;
}q[N];
inline void init(int tot){
for(int i=1;i<=tot;i++){
int u=q1[i].u,v=q1[i].v;
fa[u]=u,fa[v]=v,rk[u]=rk[v]=1;
}
}
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int u,int v){
if(rk[u]<=rk[v])fa[u]=v,rk[v]+=rk[u];
else fa[v]=u,rk[u]+=rk[v];
}
inline void contraction(int &tot,ll &now){
int cnt=0;
init(tot);
sort(q1+1,q1+tot+1,comp);
for(int i=1;i<=tot;i++){
int u=q1[i].u,v=q1[i].v;
if(find(u)!=find(v))
merge(fa[u],fa[v]),q2[++cnt]=q1[i];
}
for(int i=1;i<=cnt;i++){
int u=q2[i].u,v=q2[i].v;
fa[u]=u,fa[v]=v,rk[u]=rk[v]=1;
}
for(int i=1;i<=cnt;i++){
int u=q2[i].u,v=q2[i].v;
if(q2[i].val!=-inf&&find(u)!=find(v))
merge(fa[u],fa[v]),now+=q2[i].val;
}
cnt=0;
for(int i=1;i<=tot;i++){
int u=q1[i].u,v=q1[i].v;
if(find(u)!=find(v)){
q2[++cnt]=q1[i],p[q1[i].pos]=cnt;
q2[cnt].u=fa[q2[cnt].u];
q2[cnt].v=fa[q2[cnt].v];
}
}
for(int i=1;i<=cnt;i++)q1[i]=q2[i];
tot=cnt;
}
inline void reduction(int &tot){
int cnt=0;
init(tot);
sort(q1+1,q1+tot+1,comp);
for(int i=1;i<=tot;i++){
int u=q1[i].u,v=q1[i].v;
if(find(u)!=find(v)){
merge(fa[u],fa[v]);
q2[++cnt]=q1[i],p[q1[i].pos]=cnt;
}
else if(q1[i].val==inf)q2[++cnt]=q1[i],p[q1[i].pos]=cnt;
}
for(int i=1;i<=cnt;i++)q1[i]=q2[i];
tot=cnt;
}
#define mid ((l+r)>>1)
void cdq(int l,int r,int dep,ll now){
int tot=num[dep];
if(l==r)a[q[l].pos]=q[l].val;
for(int i=1;i<=tot;i++)e[dep][i].val=a[e[dep][i].pos];
for(int i=1;i<=tot;i++)q1[i]=e[dep][i],p[q1[i].pos]=i;
if(l==r){
q[l].ans=now;
init(tot);
sort(q1+1,q1+tot+1,comp);
for(int i=1;i<=tot;i++){
int u=q1[i].u,v=q1[i].v;
if(find(u)!=find(v))
q[l].ans+=q1[i].val,merge(fa[u],fa[v]);
}
return;
}
for(int i=l;i<=r;i++)q1[p[q[i].pos]].val=-inf;
contraction(tot,now);
for(int i=l;i<=r;i++)q1[p[q[i].pos]].val=inf;
reduction(tot);
for(int i=1;i<=tot;i++)e[dep+1][i]=q1[i];
num[dep+1]=tot;
cdq(l,mid,dep+1,now);
cdq(mid+1,r,dep+1,now);
}
#undef mid
int main(){
n=read(),m=read(),k=read();
for(int i=1;i<=m;i++){
int u=read(),v=read();a[i]=read();
e[0][i]=(edge){u,v,a[i],i};
}
for(int i=1;i<=k;i++){
q[i].pos=read(),q[i].val=read();
}
num[0]=m;
cdq(1,k,0,0);
for(int i=1;i<=k;i++){
cout<<q[i].ans<<'
';
}
return 0;
}