【OI之路】02数据结构-7动态树

LCT

文章

师兄写的
浅谈LCT实现及应用.pdf

板子

struct LCT
{
    struct Nod{int son[2],fa;bool fz;}p[MAX_N];
    LCT(){memset(p,0,sizeof p);}
    bool son(int x) {return p[p[x].fa].son[1]==x;}
    void pushdown(int x)
    {
        if(!p[x].fz) return;
        p[x].fz=0;
        int lc=p[x].son[0];p[lc].fz^=1;swap(p[lc].son[0],p[lc].son[1]);
        int rc=p[x].son[1];p[rc].fz^=1;swap(p[rc].son[0],p[rc].son[1]);
    }
    void rotate(int x)
    {
        int f=p[x].fa,ff=p[f].fa;if(p[ff].son[son(f)]==f) p[ff].son[son(f)]=x;
        int w=son(x),t=p[x].son[w^1];p[f].son[w]=t;p[x].son[w^1]=f;
        p[x].fa=ff;p[f].fa=x;p[t].fa=f;
    }
    bool isroot(int x) {return p[x].fa==0 or (p[p[x].fa].son[0]!=x and p[p[x].fa].son[1]!=x);}
    int tmp[MAX_N];
    void splay(int x)
    {
        int tot=0,now=x;while(!isroot(now)) tmp[++tot]=now,now=p[now].fa;
        tmp[++tot]=now;for(int i=tot;i>=1;i--) pushdown(tmp[i]);
        for(int f=p[x].fa;!isroot(x);rotate(x),f=p[x].fa)
            if(!isroot(f)) son(x)^son(f)?rotate(x):rotate(f);
    }

    void access(int x)
    {
        int lst=0;
        while(x!=0)
        {
            splay(x);
            p[x].son[1]=lst;p[lst].fa=x;
            lst=x;x=p[x].fa;
        }
    }
    void makeroot(int x)
    {
        access(x);splay(x);
        p[x].fz^=1;swap(p[x].son[0],p[x].son[1]);
    }
    void link(int x,int y)
    {
        makeroot(y);
        p[y].fa=x;
    }
    void cut(int x,int y)
    {
        makeroot(x);access(y);splay(y);
        p[y].son[0]=0;p[x].fa=0;
    }
    int getroot(int x)
    {
        access(x);splay(x);
        while(p[x].son[0]) pushdown(x=p[x].son[0]);
        splay(x);
        return x;
    }
}lct;

好题

CF#545F