高级数据结构-LCT

问题类型

有时我们需要用一种数据结构去维护树形结构，并且支持删边加边操作。
这时我们就需要用到LCT了。

解决方案

LCT全称是Link_Cut_Tree，也叫做动态树。
LCT其实和轻重链剖分有些相似，我们给原树中的每个节点设置一个重儿子，到偏好儿子的边称为偏好边，一段连续的偏好边称为偏好链。
我们用每个splay去维护每个偏好链，在splay中以节点的深度做为关键字。
然后splay的根向splay深度最浅点在原树中的父亲连一条虚边。

LCT的基本操作：
Access(u): 把u到原树的根的路径上所有边都变成偏好边，并且把u的偏好儿子设为空。
Make_Root(u): 把u变成原树的根。
Find_Root(u): 找出u所在的树的根。
Link(u, v): 连接u,v这条边
Cut(u, v): 割除u, v这条边

代码演示

struct LinkCutTree
{
    int rev[N + 5], val[N + 5], Son[N + 5][2], Fa[N + 5], Stack[N + 5], top;
    inline void up(int u)
    {
        val[u] = val[Son[u][0]] ^ val[Son[u][1]] ^ X[u];
    }
    inline void down(int u)
    {
        if (!rev[u]) return;
        rev[Son[u][0]] ^= 1, rev[Son[u][1]] ^= 1, rev[u] ^= 1;
        swap(Son[u][0], Son[u][1]);
    }
    inline int isroot(int u)
    {
        return (Son[Fa[u]][0] != u && Son[Fa[u]][1] != u);
    }

    void Rotate(int x)
    {
        int y = Fa[x], z = Fa[y];
        int l = Son[y][1] == x, r = l ^ 1;
        if (!isroot(y)) Son[z][Son[z][1] == y] = x;
        Son[y][l] = Son[x][r], Fa[Son[x][r]] = y;
        Son[x][r] = y, Fa[y] = x, Fa[x] = z;
        up(y), up(x);
    }
    void Splay(int x)
    {
        Stack[top = 1] = x;
        for (int y = x; !isroot(y); y = Fa[y]) Stack[++top] = Fa[y];
        per(i, top, 1) down(Stack[i]);
        while (!isroot(x))
        {
            int y = Fa[x], z = Fa[y];
            if (!isroot(y))
            {
                if ((Son[y][1] == x) ^ (Son[z][1] == y)) Rotate(x);
                else Rotate(y);
            }
            Rotate(x);
        }
    }

    inline void Access(int u)
    {
        for (int last = 0; u; last = u, u = Fa[u])
            Splay(u), Son[u][1] = last, up(u);
    }
    inline void Make_Root(int u)
    {
        Access(u), Splay(u), rev[u] ^= 1;
    }
    inline int Find_Root(int u)
    {
        Access(u), Splay(u);
        while (Son[u][0]) u = Son[u][0];
        return u;
    }

    inline void Split(int x, int y)
    {
        Make_Root(x), Access(y), Splay(y);
    }
    inline void Link(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) == x) return;
        Fa[x] = y;
    }
    inline void Cut(int x, int y)
    {
        Make_Root(x);
        if (Find_Root(y) != x || Fa[x] != y || Son[x][1]) return;
        Fa[x] = Son[y][0] = 0;
    }
}LCT;