跳转至

LCT

通用模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace Link_Cat_Tree
{
    int fa[MAX],ch[MAX][2],tag[MAX],siz[MAX],val[MAX];
    inline bool get(int i)      {return ch[fa[i]][1]==i;}
    inline bool noroot(int i)   {return ch[fa[i]][get(i)]==i;}
    inline void pushup(int i)   {siz[i]=siz[ch[i][0]]+siz[ch[i][1]]+1;}
    inline void down(int i)     {if(!i) return; tag[i]^=1,Swp(ch[i][0],ch[i][1]);}
    inline void pushdown(int i) {if(tag[i]) down(ch[i][0]),down(ch[i][1]),tag[i]=0;}
    inline void pushall(int i)  {if(noroot(i)) pushall(fa[i]); pushdown(i);}
    inline void rotate(int x)
    {
        int y=fa[x],z=fa[y];
        bool k1=get(x),k2=get(y);
        if(noroot(y)) ch[z][k2]=x; fa[x]=z;
        ch[y][k1]=ch[x][!k1],fa[ch[x][!k1]]=y;
        ch[x][!k1]=y,fa[y]=x;
        pushup(y),pushup(x);
    }
    inline void splay(int x)
    {
        pushall(x);
        while(noroot(x))
        {
            int y=fa[x];
            if(noroot(y)) (get(x)^get(y))?rotate(x):rotate(y);
            rotate(x);
        }
    }
    inline void access(int x)      {for(int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,pushup(x);}
    inline void makeroot(int x)    {access(x),splay(x),down(x);}
    inline int  findroot(int x)    {access(x),splay(x); while(ch[x][0]) pushdown(x),x=ch[x][0]; return splay(x),x;}
    inline void split(int x,int y) {makeroot(x),access(y),splay(y);}
    inline void link(int x,int y)  {makeroot(x); if(findroot(y)!=x) fa[x]=y;}
    inline void cut (int x,int y)  {makeroot(x); if(findroot(y)==x&&fa[y]==x&&!ch[y][0]) fa[y]=ch[x][1]=0,pushup(x);}
    inline bool check(int x,int y) {return findroot(x)==findroot(y);}
}