概述

LCT是一种实用数据结构（？），它滋磁维护树上信息，而且这个树是可以变换结构的。具体而言，它维护了一个Splay森林，利用Splay的功能可以维护树上信息，且可以对树结构进行拆分、连接等操作。下面介绍LCT的原理与实现。

原理与实现

一些定义

辅助树（auxiliary tree）：在LCT中，用于维护重链信息的Splay。其维护的有序性以深度为参数，即其中序遍历为该链从根到重儿子的顺序。
访问（access）：从树根出发，将根到某个节点的路径设置为重链。
重儿子（偏好儿子，preferred child）：访问到的树链的最底层节点。
重边（偏好边，preferred edge）：重链中，指向重儿子方向的边。
重链（偏好链，preferred path）：访问时走过的路径，由重边和重儿子组成。
所有的访问都会创造出重链，但是由于LCT的操作，重链可能会断掉。具体的操作需要等到讲到操作的时候才能够说清楚。
注意，辅助树是为了便于维护树上信息，其形态不一定与原树相同，我们后面会讲到辅助树与原树的关系。

树的结构

刚刚也说到了，实际上LCT维护的是一个Splay森林。一棵Splay维护的是一条重链的信息。下面是一个LCT的示意图。

图片来自Wikipedia：Link/cut tree – Wikipedia。
图片中，粗边即为重边，而细边我们将它定义为轻边。左→中表示的是以a为根的有根树访问l节点所造成的变化。右图展示的是Splay的划分。
我们说，Splay维护的是重链信息，而当前Splay和原树中重链顶的父节点通过轻边（右图虚线箭头）来连接。
从现在开始，文章内容默认你已经会使用Splay的操作。如果Splay仍不会，可以参考Splay原理与实现 | KSkun’s Blog一文。

LCT的核心：访问（access）

访问，即从树根出发，将树根到某节点x的路径设置为重链的操作。要实现这个操作，我们需要将这一排点加入到一个Splay中。
实现上，我们要断掉链上的点与之前重儿子的连接，将其合并到一个Splay中。我们从重儿子x向树根处理，每次将节点splay到所在辅助树的根，此时该点的右子树为以前重链上需要切掉的一段。切断这条重边，并将右儿子的连边设置为向当前重儿子的重边即可。
实现上，我们统一用fa这一变量来存储父亲的信息，也就是说这个fa可能指的并非所在Splay的父节点，而是轻边的父节点。但是每个节点的儿子信息则完全是Splay中的儿子信息，即轻边的儿子不会在父节点有记录。因此我们只需更改每个节点的右儿子即可，并不需要重置右儿子的父亲信息。

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

换根（make_root）

换根，即将原树转换为以某节点x为树根的有根树。
我们可以访问该节点，并将其splay至根。由于Splay内部的有序以深度为依据，x只有左儿子，此时表示x在重链的底端。我们对这棵Splay进行翻转，x就变为重链的顶端，即原树树根。

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

找根（find_root）

找根，即找到某节点x所在原树的树根。
先访问该节点，splay至根。此时这条链上深度最小的点即为原树树根。因此我们只需找到最左的左儿子即可。

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

分离树链（split）

分离树链，即将原树中某节点u到v的路径分离出来。
我们考虑将链的一端u设为树根，并访问v，将v splay到根。此时对于这条树链，在u、v所在的Splay上的体现即为v及v的左子树。

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

连接原树（link）

连接原树，即将某节点u、v所在的原树通过边(u, v)连接起来。
先将其中一点u设为原树根，以轻边接到v上即可。如果此处利用split，效果其实是一样的。

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

切断原树（cut）

切断原树，即将本相连的节点u、v之间的边切断。
先将这条边split出来，然后切断父子关系即可。如果左儿子不是u或者左儿子有右儿子，那么表示不存在(u, v)这条边。

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[tr[v].ch[0]].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0;
}

改变点值（modify）

你需要把该点提至整棵树的树根，再做修改，这样可以避免修改后还要向上更新根的信息。

inline void modify(int u, int w) {
    access(u);
    splay(u);
    tr[u].val = w; // 更改值
    update(u);
}

与单独Splay操作的区别

由于我们用fa混着存两种边关系，即轻儿子、重儿子，我们不好判断Splay根的位置。下面是一种判断是否为Splay根的方法。

inline bool isroot(int p) {
    int fa = tr[p].fa;
    return tr[fa].ch[0] != p && tr[fa].ch[1] != p;
}

对于Splay中常见的旋转（rotate）、伸展（splay）操作，实现上有些许区别。主要原因判断Splay根的方式变了。

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p); // 对p只update一次，优化常数
}

辅助树与原树的关系

原树在LCT中其实是剖成几条树链的，每条树链一个Splay。原树的结构中树链顺序，则为Splay的顺序，父子关系也依赖着轻重边来进行管理。但是LCT这个奇妙的Splay森林结构并不和原来的有根树完全相同，Splay根和树根也并不相同。
最开始看LCT就是在这里搞不懂的。而且直到现在我也不知道应该怎么写这段内容GG。

例题：【P3690】【模板】Link Cut Tree （动态树） – 洛谷

题目描述

1. 求链点权异或和
2. 连接树边
3. 断开树边
4. 改变点权

题解

我们在节点处维护一个子树异或和（Splay意义上的子树），每次查询split以后查。
修改操作则先访问它并且把这个点splay到根再改。

代码

// Code by KSkun, 2018/4
#include <cstdio>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 300005;

struct Node {
    int ch[2], fa, val, xsum;
    bool rev;
} tr[MAXN];

inline bool isleft(int p) {
    return tr[tr[p].fa].ch[0] == p;
}

inline bool isroot(int p) {
    return tr[tr[p].fa].ch[0] != p && tr[tr[p].fa].ch[1] != p;
}

inline void update(int p) {
    tr[p].xsum = tr[p].val ^ tr[tr[p].ch[0]].xsum ^ tr[tr[p].ch[1]].xsum;
}

inline void reverse(int p) {
    std::swap(tr[p].ch[0], tr[p].ch[1]);
    tr[p].rev ^= 1;
}

inline void pushdown(int p) {
    if(tr[p].rev) {
        if(tr[p].ch[0]) reverse(tr[p].ch[0]);
        if(tr[p].ch[1]) reverse(tr[p].ch[1]);
        tr[p].rev ^= 1;
    }
}

int sta[MAXN], stop;

inline void pushto(int p) {
    stop = 0;
    while(!isroot(p)) {
        sta[stop++] = p;
        p = tr[p].fa;
    }
    sta[stop++] = p;
    while(stop) {
        pushdown(sta[--stop]);
    }
}

inline void rotate(int p) {
    bool t = !isleft(p); int fa = tr[p].fa, ffa = tr[fa].fa;
    tr[p].fa = ffa; if(!isroot(fa)) tr[ffa].ch[!isleft(fa)] = p;
    tr[fa].ch[t] = tr[p].ch[!t]; tr[tr[fa].ch[t]].fa = fa;
    tr[p].ch[!t] = fa; tr[fa].fa = p;
    update(fa);
}

inline void splay(int p) {
    pushto(p);
    for(int fa = tr[p].fa; !isroot(p); rotate(p), fa = tr[p].fa) {
        if(!isroot(fa)) rotate(isleft(fa) == isleft(p) ? fa : p);
    }
    update(p);
}

inline void access(int p) {
    for(int q = 0; p; q = p, p = tr[p].fa) {
        splay(p);
        tr[p].ch[1] = q;
        update(p);
    }
}

inline void makert(int p) {
    access(p);
    splay(p);
    reverse(p);
}

inline int findrt(int p) {
    access(p);
    splay(p);
    while(tr[p].ch[0]) p = tr[p].ch[0];
    return p;
}

inline void split(int u, int v) {
    makert(u);
    access(v);
    splay(v);
}

inline void link(int u, int v) {
    split(u, v);
    tr[u].fa = v;
}

inline void cut(int u, int v) {
    split(u, v);
    if(tr[v].ch[0] != u || tr[u].ch[1]) return;
    tr[u].fa = tr[v].ch[0] = 0;
}

inline void modify(int u, int w) {
    access(u);
    splay(u);
    tr[u].val = w;
    update(u);
}

int n, m, op, x, y;

int main() {
    n = readint(); m = readint();
    for(int i = 1; i <= n; i++) {
        tr[i].val = tr[i].xsum = readint();
    }
    while(m--) {
        op = readint(); x = readint(); y = readint();
        switch(op) {
        case 0:
            split(x, y);
            printf("%d\n", tr[y].xsum);
            break;
        case 1:
            link(x, y);
            break;
        case 2:
            cut(x, y);
            break;
        case 3:
            modify(x, y);
        }
    }
    return 0;
}

参考资料

• P3690 【模板】Link Cut Tree （动态树） 题解
• [Link-Cut-Tree]【学习笔记】 – Candy? – 博客园
• Link/cut tree – Wikipedia
• 动态树（Link-Cut Tree）学习小结 – CSDN博客
• [Luogu3203]：HNOI2010弹飞绵羊 – CSDN博客