题目

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

思路

代码

#include
    
     #define M 50005#define LL long longusing namespace std;const LL inf=1e9;int n,m,Q;struct S{    int fa[M],rk[M],top;    struct node{int x,y;}stk[M];    void Init(){        for(int i=1;i<=n;i++)fa[i]=i,rk[i]=1;top=0;    }    int getfa(int x){        return fa[x]==x?x:getfa(fa[x]);    }    void Union(int x,int y){        int rtx=getfa(x),rty=getfa(y);        if(rtx==rty)return;        if(rk[rtx]
     
      wk,tmp;LL ans[M];bool mark[M],used[M];struct node{int id;LL v;}A[M];void Reduction(int l,int r){    for(int i=l;i<=r;i++)mark[A[i].id]=1;    for(int i=0;i
      
       bc=wk;    int ned=bcj.top;    co+=Contraction(l,r);Reduction(l,r);    int mid=(l+r)>>1;    solve(l,mid,co);solve(mid+1,r,co);    while(bcj.top!=ned)bcj.undo();    wk=bc;bc.clear();}int main(){    scanf("%d%d%d",&n,&m,&Q);bcj.Init();    for(int i=1;i<=m;i++){        scanf("%d%d%lld",&E[i].x,&E[i].y,&E[i].v);E[i].id=i;        wk.push_back(E[i]);    }    for(int i=1;i<=Q;i++)scanf("%d%lld",&A[i].id,&A[i].v);    solve(1,Q,0);    for(int i=1;i<=Q;i++)        printf("%lld\n",ans[i]);    return 0;}