题目大意

给你一个无向连通图，有两种边，为\(k-x\)和\(k+x\)的形式。

有一堆询问，问\(x\)为某个值的时候的最小生成树。

---

思考历程

有过一些猜想，但被自己推翻了。

没有想出来，于是只能打暴力。

---

正解

首先有个比赛时就想到的一个很显然的结论：

肯定是正边和负边分别做一次最小生成树，然后用这些树边来生成新的最小生成树。

当时我是这么想的：可以先对正边做一次最小生成树，然后一条一条负边加进去，可以用\(LCT\)维护。最终形成的一定是最优的。所以只有正边的最小生成树的边有意义。反过来，只有负边的最小生成树的边有意义。

于是就只有两棵树的边有意义。

所以就先做一遍最小生成树。然后对正边建立\(LCT\)。

将负边排序，一个一个加进去。每次替换路径上权值最大的正边，并且记录替换的时候的\(x\)的下界。

搞完之后将\(x\)的下界排个序，就可以得到各个时段的最小生成树。

为什么是正确的呢？

如果有两条边，它们端点覆盖的路径的最大边是相同的（在没有进行任何加边操作和删边操作的时候）。很显然，更小的那个会优先替代（时间上也是它更小），而更大的那个会替代路径上其它的比较大的边。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 100010#define M 200010#define INF 2000000000#define ll long longint n,A,B;struct edge{    int u,v,len;} ea[M],eb[M];bool cmpe(const edge &a,const edge &b){return a.len
       
        push();if (rev) rev=0,c[0]->rvs(),c[1]->rvs();}    inline bool getson(){return fa->c[0]!=this;}    inline void upd(){mx=(c[0]->mx->len>c[1]->mx->len?c[0]->mx:c[1]->mx),mx=(mx->len
        
         isr)            y->isr=0,isr=1;        else            y->fa->c[y->getson()]=this;        bool k=getson();        fa=y->fa;        y->c[k]=c[!k],c[!k]->fa=y;        c[!k]=y,y->fa=this;        mx=y->mx,y->upd();    }    inline void splay(){        push();        for (;!isr;rotate())            if (!fa->isr)                getson()!=fa->getson()?rotate():fa->rotate();    }    inline Node *access(){        Node *x=this,*y=null;        for (;x!=null;y=x,x=x->fa){            x->splay();            x->c[1]->isr=1;            y->isr=0;            x->c[1]=y;            x->upd();        }        return y;    }    inline Node *mroot(){        Node *res=access();        res->rvs();        return res;    }    inline void link(Node *y){y->mroot()->fa=this;}} d[N],eda[N],edb[N];int tim[N],con[N],p[N];bool cmpp(int a,int b){return tim[a]
         
          mx->len==-INF){ tim[i]=INF; continue; } tim[i]=(eb[i].len-t->mx->len-1>>1)+1; con[i]=eb[i].len-t->mx->len; t=t->mx; d[ea[t-eda].u].mroot(); d[ea[t-eda].v].access(); t->splay(); t->c[0]->isr=t->c[1]->isr=1; t->c[0]->fa=t->c[1]->fa=null; edb[i]={null,null,null,0,1,-INF,null}; edb[i].link(&d[u]); edb[i].link(&d[v]); } sort(p+1,p+B+1,cmpp); for (int i=1;i<=Q;++i) scanf("%d",&q[i].x),q[i].num=i; sort(q+1,q+Q+1,cmpq); for (int i=1,j=1,k=n-1;i<=Q;++i){ for (;j<=B && tim[p[j]]<=q[i].x;++j){ sum+=con[p[j]]; k-=2; } ans[q[i].num]=sum+(ll)k*q[i].x; } for (int i=1;i<=Q;++i) printf("%lld\n",ans[i]); return 0;}
         
        
       
      
     
    

---

总结

有了结论，一切都好说……

我一开始就应该猜结论，拍验证……