【UOJ#207】共价大爷游长沙

mrsrz 12月 10, 2019

随机权值，LCT 维护子树信息

题目大意：

给定一棵树，和一个可重路径集合 $S$，要支持以下操作：

修改树上的一条边，保证操作合法且修改完仍然是一棵树。
将一条路径加入 $S$。
删除 $S$ 中的一条路径，保证原来存在。
给定一条边，询问是否 $S$ 中所有路径都经过这条边。

题解：

对于查询，我们如果把这条边断掉，那么树会分成两棵树。如果这条边必经，那么两棵树的任意一棵里，都包含 $S$ 中每条路径的恰好一个端点。

那么我们对每条路径都赋一个随机的权值 $v$，并对路径的两个端点都异或上 $v$。

然后用 LCT 实现动态加边删边，维护子树异或和。

查询的时候，如果断掉边后，一棵子树的异或和恰好等于当前 $S$ 中所有路径的异或和，则说明该边必经。否则就说明有一条路径两个端点都不在子树内或都在子树内（异或抵消），该边不必经。

出错的概率极低，可以忽略。

时间复杂度 $O((n+m)\log n)$。

Code：

#include<iostream>
#include<ctime>
#include<random>
using namespace std;
typedef unsigned long long LL;
const int N=3e5+8;
mt19937_64 mt(time(0));
int T,n,m;
int U[N],V[N],t0t;LL W[N];
namespace lct{
    int ch[N][2],fa[N],sz[N];
    LL val[N],v_[N],xv[N];
    bool tag[N];
    inline bool ckr(int x,int p=1){return ch[fa[x]][p]==x;}
    inline bool isroot(int x){return!(ckr(x)||ckr(x,0));}
    inline void flip(int x){swap(ch[x][0],ch[x][1]),tag[x]^=1;}
    inline void pushdown(int x){
        if(tag[x]){
            if(ch[x][0])flip(ch[x][0]);
            if(ch[x][1])flip(ch[x][1]);
            tag[x]=0;
        }
    }
    inline void update(int x){
        sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
        xv[x]=val[x]^v_[x]^xv[ch[x][0]]^xv[ch[x][1]];
    }
    inline void rotate(int x){
        int y=fa[x],z=fa[y],k=ckr(x);
        if(!isroot(y))ch[z][ckr(y)]=x;
        fa[x]=z,fa[y]=x,fa[ch[x][!k]]=y;
        ch[y][k]=ch[x][!k],ch[x][!k]=y,update(y);
    }
    inline void splay(int x){
        static int sta[N],top;sta[top=1]=x;
        for(int y=x;!isroot(y);sta[++top]=y=fa[y]);
        while(top)pushdown(sta[top--]);
        for(;!isroot(x);rotate(x))
            if(!isroot(fa[x]))rotate((ckr(x)^ckr(fa[x]))?x:fa[x]);
        update(x);
    }
    inline void access(int x){
        for(int t=0;x;ch[x][1]=t,t=x,x=fa[x])splay(x),v_[x]^=xv[t]^xv[ch[x][1]];
    }
    inline void makeroot(int x){access(x),splay(x),flip(x);}
    inline void split(int x,int y){makeroot(x),access(y),splay(y);}
    inline void link(int x,int y){makeroot(x),makeroot(y),fa[x]=y,v_[y]^=xv[x],update(y);}
    inline void cut(int x,int y){split(x,y),ch[y][0]=fa[x]=0,update(y);}
    inline void modify(int x,LL v){makeroot(x),val[x]^=v,update(x);}
    inline bool ask(int x,int y,LL X){
        cut(x,y);
        bool ans=xv[x]==X;
        link(x,y);
        return ans;
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T>>n>>m;
    for(int i=1;i<=n;++i)
        lct::sz[i]=1;
    for(int i=1;i<n;++i){
        int x,y;
        cin>>x>>y;
        lct::link(x,y);
    }
    LL X=0;
    while(m--){
        int op;
        cin>>op;
        switch(op){
            case 1:{
                       int x,y;
                       cin>>x>>y;
                       lct::cut(x,y);
                       cin>>x>>y;
                       lct::link(x,y);
                       break;
                   }
            case 2:{
                       int x,y;
                       cin>>x>>y;
                       U[++t0t]=x,V[t0t]=y,W[t0t]=mt();
                       lct::modify(x,W[t0t]);
                       lct::modify(y,W[t0t]);
                       X^=W[t0t];
                       break;
                   }
            case 3:{
                       int id;
                       cin>>id;
                       lct::modify(U[id],W[id]);
                       lct::modify(V[id],W[id]);
                       X^=W[id];
                       break;
                   }
            case 4:{
                       int x,y;
                       cin>>x>>y;
                       cout<<(lct::ask(x,y,X)?"YES":"NO")<<'\n';
                   }
        }
    }
    return 0;
}