【数据结构】LinkCutTree

和重链剖分的概念有点点像。或者应该叫做实链剖分。

LCT维护的“原树”并非是一棵树，而是一片森林。森林中的树可以切成各种形状的树，也可以把不同的树合并。LCT内部的“辅助树”也不是一棵树，而是一片（更大的）Splay森林。

原树是一棵有根树。支持以下操作：
1、对原树节点x和节点y的链更新某信息
2、对原树节点x和节点y的链查询某信息
3、重新指定原树的根节点
4、删除原树的边x-y
5、添加原树的边x-y，其中y是深度更小的节点

LCT维护一片Splay森林，其中每一棵Splay代表原树的一条深度单调递增/单调递减的链（也就是说不拐弯的链）。每一棵Splay的中序遍历是原树的链顶到链底。所以每个节点的实儿子是唯一的，父亲也是唯一的。

实儿子：原树中，当前节点的儿子，且当前节点处于同一棵Splay中，当前节点知道它的实儿子是谁，实儿子也知道其父亲是谁。
虚儿子：原树中，当前节点的儿子，且当前节点不处于同一棵Splay中，当前节点并不知道它的虚儿子有哪些，但是虚儿子知道其父亲是谁。

struct LinkCutTree {

    static const int MAXN = 2e5 + 10;

    int ch[MAXN][2], pa[MAXN];
    int siz[MAXN], rev[MAXN];
    int val[MAXN], sum[MAXN];

    inline void PushUp(int x) {
        siz[x] = 1 + siz[ch[x][0]] + siz[ch[x][1]];
        sum[x] = val[x] ^ sum[ch[x][0]] ^ sum[ch[x][1]];
    }

    inline void PushDown(int x) {
        if(rev[x]) {
            swap(ch[x][0], ch[x][1]);
            rev[ch[x][0]] ^= 1, rev[ch[x][1]] ^= 1, rev[x] = 0;
        }
    }

    inline bool IsRoot(int x) {
        return ch[pa[x]][0] != x && ch[pa[x]][1] != x;
    }

    void Rotate(int x) {
        int y = pa[x], z = pa[y];
        int l = (ch[y][0] != x), r = l ^ 1;
        if(!IsRoot(y))
            ch[z][ch[z][0] != y] = x;
        pa[x] = z, pa[y] = x, pa[ch[x][r]] = y;
        ch[y][l] = ch[x][r], ch[x][r] = y;
        PushUp(y), PushUp(x);
    }

    void Splay(int x) {
        static int stk[MAXN], top;
        stk[++top] = x;
        for(int i = x; !IsRoot(i); i = pa[i])
            stk[++top] = pa[i];
        while(top)
            PushDown(stk[top--]);
        for(; !IsRoot(x); Rotate(x)) {
            int y = pa[x], z = pa[y];
            if(!IsRoot(y))
                Rotate(((ch[y][0] == x) != (ch[z][0] == y)) ? x : y);
        }
    }

    void Access(int x) {
        for(int t = 0; x; t = x, x = pa[x])
            Splay(x), ch[x][1] = t, PushUp(x);
    }

    void MakeRoot(int x) {
        Access(x), Splay(x), rev[x] ^= 1;
    }

    int FindRoot(int x) {
        Access(x), Splay(x);
        while(ch[x][0])
            x = ch[x][0];
        return x;
    }

    void Select(int x, int y) {
        MakeRoot(x), Access(y), Splay(y);
    }

    void Cut(int x, int y) {
        Select(x, y);
        if(ch[y][0] == x && ch[x][1] == 0)
            ch[y][0] = 0, pa[x] = 0;
    }

    void Cut2(int x, int y) {
        if(FindRoot(x) == FindRoot(y))
            Cut(x, y);
    }

    void Link(int x, int y) {
        MakeRoot(x), pa[x] = y;
    }

    void Link2(int x, int y) {
        if(FindRoot(x) != FindRoot(y))
            Link(x, y);
    }

    void Update(int x, int v) {
        Select(x, x), val[x] = v, PushUp(x);
    }

} lct;

Access：把x到原树的根节点的路径变为实路径
MakeRoot：指定原树的根节点为x（换根）
FindRoot：找x在辅助树的树根，也就是x在原树的实链的链顶
Select：把x和y之间的路径切成一个Splay，根是y。
Cut：切断x和y的边
Cut2：假如x和y之间有边，则切断x和y的边
Link：连接x和y的边
Link2：假如x和y之间不连通，则连接x和y的边
Update：更新点x的权值为v

【数据结构】LinkCutTree

原文：https://www.cnblogs.com/purinliang/p/14403506.html