Link-Cut Tree（LCT）

luckydrawbox · 2023-08-05 20:27:52 · 个人记录

宏定义

变量

函数

代码

#define pl a[p].ch[0]
#define pr a[p].ch[1]
struct LCT{
    struct Tree{
        int ch[2],fa;
        int val,sum,rev;
    }a[N];
    bool isroot(int p){
        return a[a[p].fa].ch[0]!=p&&a[a[p].fa].ch[1]!=p;
    }
    void pushup(int p){
        a[p].sum=a[pl].sum^a[p].val^a[pr].sum;
    }
    void pushrev(int p){
        swap(pl,pr);a[p].rev^=1;
    }
    void pushdown(int p){
        if(a[p].rev){
            if(pl)pushrev(pl);
            if(pr)pushrev(pr);
            a[p].rev=0;
        }
    }
    int get(int p){
        return a[a[p].fa].ch[1]==p;
    }
    void update(int p){
        if(!isroot(p))update(a[p].fa);
        pushdown(p);
    }
    void rotate(int p){
        int fp=a[p].fa,ffp=a[fp].fa;
        int ty=get(p);
        if(!isroot(fp))a[ffp].ch[get(fp)]=p;a[p].fa=ffp;
        a[fp].ch[ty]=a[p].ch[ty^1];
        if(a[p].ch[ty^1])a[a[p].ch[ty^1]].fa=fp;
        a[p].ch[ty^1]=fp;a[fp].fa=p;
        pushup(fp);pushup(p);
    }
    void splay(int p){
        update(p);
        for(int fp;!isroot(p);rotate(p)){
            fp=a[p].fa;
            if(!isroot(fp))
                rotate(get(fp)^get(p)?p:fp);
        }
        pushup(p);
    }
    void access(int p){
        for(int q=0;p;p=a[q=p].fa)
            splay(p),pr=q,pushup(p);
    }
    void makeroot(int p){
        access(p);splay(p);pushrev(p);
    }
    int findroot(int p){
        access(p);splay(p);
        while(pl)pushdown(p),p=pl;
        splay(p);return p;
    }
    void split(int p,int q){
        makeroot(p);access(q);splay(q);
    }
    void link(int p,int q){
        makeroot(p);if(p!=findroot(q))a[p].fa=q;
    }
    void cut(int p,int q){
        makeroot(p);
        if(findroot(q)==p&&a[q].fa==p&&!a[q].ch[0]){
            a[q].fa=pr=0;
            pushup(p);
        }
    }
    void change(int p,int val){
        splay(p);a[p].val=val;pushup(p);
    }
}lct;