CC++ & Algorithm

动态树（Link-Cut Tree）简介

极难4
语言版本：通用
概述：用Splay树维护森林上的路径，支持连边、断边和路径查询，让树动起来。

让树木自由生长：动态树（Link-Cut Tree）完全入门

你有没有想过，如果一棵树可以随时“长出”新树枝、折断旧树枝，而且你还能快速知道任意两个枝杈之间最长或者最短的距离，该怎么办？普通的树链剖分（树剖）只能处理静态的树——树一旦建好就不能再改。但现实中的关系网、社交网络、甚至游戏里的技能树都是会变的。动态树（Link-Cut Tree，简称LCT） 就是专门解决这种动态森林问题的“神兵利器”。

LCT的核心思想是：用Splay树来维护树上的“实链”，通过 access 操作动态地改变虚实关系，从而实现连边、断边、换根、路径查询等操作，每次操作的平均时间复杂度只有 O(log n)（基于Splay的势能分析）。

本文将从零开始，带你理解LCT的每一个关键概念，配合生活实例、图解和完整代码，让你轻松掌握这个高级数据结构。

1. LCT 能做什么？

  • link(u, v)：在 u 和 v 之间连一条边（前提是它们原本不在同一棵树里）。
  • cut(u, v)：断开 u 和 v 之间的边（前提是边确实存在）。
  • find_root(u)：找到 u 所在树的根节点。
  • makeroot(u)：把 u 变为它所在树的根（树换根）。
  • split(u, v)：把 u 到 v 的路径“提取”出来，方便查询路径上的信息（比如最大值、和、异或和等）。
  • 单点修改：更新某个节点的权值，并更新路径信息。

举个例子：你正在设计一个社交网络，每个用户是一个节点，好友关系是边。用户可以加好友（link）、删除好友（cut），你可以随时查询两个用户之间是否存在路径（连通性），或者他们之间所有用户的“活跃度”总和（路径查询）。LCT就是完成这些任务的利器。

2. 生活中的比喻：从“排队”到“实链”

想象班级排队做操：同学们站成一列，老师每次可以叫一个同学“出列”变成排头，也可以把两列合并成一列。这里的“列”就是一条链，而LCT中的 Splay树 就是把一条链上的节点按深度顺序存起来（中序遍历就是从上到下）。而整个森林由很多条这样的链组成，通过虚边连接。

  • 实链：当前被选中、用Splay树维护的一段路径。比如老师正在管理的这一列。
  • 虚边：表示两条实链之间的连接（但不在同一棵Splay树中）。比如两列排队的人虽然属于同一个班级，但暂时没有合并成一列。

LCT的精髓就在于：你可以通过 access 操作，把某个节点到根节点的路径上所有虚边都变成实边，从而提取出一条完整的实链。

3. 核心概念详解

3.1 实链剖分与辅助树

  • 实链剖分：每个节点最多有一条实边连向它的重儿子（注意这里是动态的，根可以变）。其余的边都是虚边。
  • 辅助树（Auxiliary Tree）：由多棵Splay树组成，每一棵Splay树维护一段实链。Splay树的中序遍历对应链上节点从上到下的顺序。
  • 认父不认子：虚边只记录父指针（fa），但不记录子指针。也就是说，Splay树的根节点通过 fa 指向它在原树中的父节点（如果存在），但那个父节点并不知道有这个子节点（除非通过实链）。

生活例子：假设一个班级分成好几个小组，每个小组内成员手拉手站成一列（实链），组长（Splay树的根）则和上一组的组长通过“眼神示意”连接（虚边）。access 操作就是让班长下令：“所有小组列队，从你开始一直到最前面的人，全部手拉手站成一个大长队！”

3.2 核心操作：access

access(x) 是LCT中最基础也最重要的操作。它的作用是把从 x 到它所在树的根节点之间的路径变成一条实链，并且 x 是这条链的最后一个节点（深度最大）。做法如下：

  1. 从 x 开始，不断重复以下步骤，直到 x 变成根（即 x 的父指针为0）：
    • 把 x 在它所在的Splay树中旋转到根（splay(x)）。
    • 把 x 的右儿子改成上一次操作处理过的节点（即之前那条链的头部），这样就相当于把虚边变成了实边。
    • 更新节点信息（pushup），然后 x 沿着虚边跳到它的父节点。

简单记忆：access(x) = 把 x 到根的路径全部打通，变成一条实实在在的链。

3.3 核心操作：makeroot

makeroot(x) 让 x 成为它所在树的根。做法：

  1. 先 access(x)，把 x 到原来根的路径打通。
  2. 再 splay(x)，让 x 成为Splay树的根。
  3. 最后给 x 打上翻转标记（rev），这样整棵Splay树的中序就反过来了，原来深度最大的 x 变成了深度最小（即根）。

为什么可以这样？ 因为Splay树的中序遍历代表实链从上到下的顺序，翻转后顺序相反，深度也就反过来了。

3.4 其他操作：find_root、split、link、cut

  • find_root(x)：先 access(x) 打通路径，再 splay(x)，然后一直往左儿子走（因为中序遍历最左边的节点是深度最小的节点，即根），走到叶子就是根。注意最后要 splay 一下该节点，保证复杂度。
  • split(u, v)：提取 u 到 v 的路径。做法：makeroot(u)，然后 access(v)，最后 splay(v)。此时 v 的Splay树中存的就是 u 到 v 路径上的所有节点，t[v].sum（或别的信息）就是路径总信息。
  • link(u, v)：在 u 和 v 之间加边。先 makeroot(u)，如果 find_root(v) != u（说明它们不在一棵树里），则把 u 的父指针指向 v（加一条虚边）。
  • cut(u, v)：断开边 (u, v)。先 makeroot(u)，再 access(v) 并 splay(v)。此时如果 u 是 v 的左儿子（且 u 没有右子树），说明它们直接相连，就可以断开：把 v 的左儿子置0，u 的父指针置0，并更新信息。

判断是否直接相连的条件：

  • find_root(v) == u（它们在同一棵树里）。
  • t[v].fa == u 且 t[v].ch[0] == 0（因为 makeroot(u) 后，u 是根，v 在它的右子树里，并且 u 到 v 是直接边，所以 v 的左儿子应该为空，否则 v 有更深的子孙）。

4. 新手最容易犯的 5 个错误

  1. 忘记 pushdown：在 splay 之前，必须把从根到当前节点的路径上的所有翻转标记都下传（一般用栈存储路径）。否则翻转标记没下传，旋转会导致树结构错误。
  2. access 时没有更新右儿子：每一步必须把 last 赋给当前节点的右儿子，并 pushup，否则新链的边没连上。
  3. cut 时条件判断太宽松：不能只判断 find_root(v) == u，还必须验证 t[v].fa == u && t[v].ch[0] == 0。否则可能误删了非直接边。
  4. isroot 判断错误：一个节点是Splay树的根，当且仅当它的父指针指向的节点（fa[x]）的左右儿子都不是它。注意：虚边和实边的父指针都在 fa 里，所以用 t[t[x].fa].ch[0] != x && t[t[x].fa].ch[1] != x。
  5. 单点修改后忘记 pushup：修改节点值后，一定要 splay 该节点（确保信息正确），然后 pushup。或者调用 splay(u) 后再修改，然后再 pushup。

5. 完整代码示例（支持路径异或和）

下面给出 C++ 和 Python 的完整实现，以 路径异或和 为例（你可以轻松改成最大值、和等）。代码中每一行变量都加了中文注释。

5.1 C++ 代码

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100005;  // 最大节点数

struct Node {
    int ch[2];   // 左右儿子，0:左，1:右
    int fa;      // 父指针（包括实边和虚边）
    int val;     // 节点权值
    int sum;     // 子树异或和
    int rev;     // 翻转标记（懒标记）
} t[MAXN];

// 判断 x 是不是它所在Splay树的根（不是原树根）
bool isroot(int x) {
    int f = t[x].fa;
    return t[f].ch[0] != x && t[f].ch[1] != x;
}

// 上传信息：计算异或和
void pushup(int x) {
    t[x].sum = t[x].val ^ t[t[x].ch[0]].sum ^ t[t[x].ch[1]].sum;
}

// 翻转一个子树
void pushrev(int x) {
    if (!x) return;
    swap(t[x].ch[0], t[x].ch[1]);  // 交换左右儿子
    t[x].rev ^= 1;                 // 标记翻转
}

// 下传懒标记
void pushdown(int x) {
    if (t[x].rev) {
        pushrev(t[x].ch[0]);
        pushrev(t[x].ch[1]);
        t[x].rev = 0;
    }
}

// 旋转（左旋或右旋，根据k决定）
void rotate(int x) {
    int y = t[x].fa;
    int z = t[y].fa;
    int k = (t[y].ch[1] == x);  // 0:左旋，1:右旋
    if (!isroot(y)) t[z].ch[t[z].ch[1] == y] = x;
    t[x].fa = z;

    t[y].ch[k] = t[x].ch[k ^ 1];
    if (t[x].ch[k ^ 1]) t[t[x].ch[k ^ 1]].fa = y;

    t[x].ch[k ^ 1] = y;
    t[y].fa = x;

    pushup(y);
    pushup(x);
}

// 把 x 旋转到它所在Splay树的根
void splay(int x) {
    vector<int> stk;  // 栈用于保存从根到x的路径
    int y = x;
    stk.push_back(y);
    while (!isroot(y)) y = t[y].fa, stk.push_back(y);
    // 从根到x依次下传标记
    while (!stk.empty()) pushdown(stk.back()), stk.pop_back();

    while (!isroot(x)) {
        int y = t[x].fa, z = t[y].fa;
        if (!isroot(y)) {
            // 如果是折线形，先转x；如果是直线形，先转y
            if ((t[z].ch[0] == y) ^ (t[y].ch[0] == x)) rotate(x);
            else rotate(y);
        }
        rotate(x);
    }
    pushup(x);
}

// 打通 x 到根的路径，变成实链
void access(int x) {
    int last = 0;  // 上一次操作处理完的节点（即新链的头）
    for (; x; x = t[x].fa) {
        splay(x);
        t[x].ch[1] = last;  // 把右儿子改成上次的链（虚变实）
        pushup(x);
        last = x;           // 更新last
    }
}

// 让 x 成为原树的根
void makeroot(int x) {
    access(x);
    splay(x);
    pushrev(x);  // 翻转整棵Splay树，深度颠倒
}

// 找到 x 所在原树的根
int find_root(int x) {
    access(x);
    splay(x);
    while (t[x].ch[0]) pushdown(x), x = t[x].ch[0];  // 一直往左
    splay(x);  // 保证势能分析
    return x;
}

// 提取 u 到 v 的路径，结果存在 v 的Splay树中
void split(int u, int v) {
    makeroot(u);
    access(v);
    splay(v);
}

// 连接 u 和 v（加边）
void link(int u, int v) {
    makeroot(u);
    if (find_root(v) != u) t[u].fa = v;  // 加一条虚边
}

// 断开 u 和 v 之间的边
void cut(int u, int v) {
    makeroot(u);
    // 判断是否直接相连
    if (find_root(v) == u && t[v].fa == u && !t[v].ch[0]) {
        t[u].ch[1] = 0;  // 右子树置空
        t[v].fa = 0;     // 父指针清0
        pushup(u);
    }
}

int main() {
    int n, m;          // n:节点数，m:操作数
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> t[i].val;    // 输入节点权值
        t[i].sum = t[i].val;
    }
    while (m--) {
        int op, u, v;
        cin >> op >> u >> v;
        if (op == 0) {               // 查询u到v路径异或和
            split(u, v);
            cout << t[v].sum << endl;
        } else if (op == 1) {        // 连接u和v
            link(u, v);
        } else if (op == 2) {        // 断开u和v
            cut(u, v);
        } else {                     // 修改u的权值为v
            splay(u);
            t[u].val = v;
            pushup(u);
        }
    }
    return 0;
}

5.2 Python 代码

import sys
sys.setrecursionlimit(1 << 25)  # 防止递归深度不够

class LCT:
    def __init__(self, n):
        self.n = n
        self.ch = [[0, 0] for _ in range(n + 1)]  # 左右儿子
        self.fa = [0] * (n + 1)                    # 父指针
        self.val = [0] * (n + 1)                   # 节点权值
        self.sum = [0] * (n + 1)                   # 子树异或和
        self.rev = [0] * (n + 1)                   # 翻转标记

    def isroot(self, x):
        # 判断 x 是不是Splay树的根
        f = self.fa[x]
        return f == 0 or (self.ch[f][0] != x and self.ch[f][1] != x)

    def pushup(self, x):
        self.sum[x] = self.val[x] ^ self.sum[self.ch[x][0]] ^ self.sum[self.ch[x][1]]

    def pushrev(self, x):
        if x == 0:
            return
        self.ch[x][0], self.ch[x][1] = self.ch[x][1], self.ch[x][0]
        self.rev[x] ^= 1

    def pushdown(self, x):
        if self.rev[x]:
            self.pushrev(self.ch[x][0])
            self.pushrev(self.ch[x][1])
            self.rev[x] = 0

    def rotate(self, x):
        y = self.fa[x]
        z = self.fa[y]
        k = 1 if self.ch[y][1] == x else 0   # 0:左旋，1:右旋
        if not self.isroot(y):
            self.ch[z][1 if self.ch[z][1] == y else 0] = x
        self.fa[x] = z
        self.ch[y][k] = self.ch[x][k ^ 1]
        if self.ch[x][k ^ 1]:
            self.fa[self.ch[x][k ^ 1]] = y
        self.ch[x][k ^ 1] = y
        self.fa[y] = x
        self.pushup(y)
        self.pushup(x)

    def splay(self, x):
        # 先用栈保存路径，依次下传标记
        stk = []
        y = x
        stk.append(y)
        while not self.isroot(y):
            y = self.fa[y]
            stk.append(y)
        while stk:
            self.pushdown(stk.pop())
        while not self.isroot(x):
            y = self.fa[x]
            z = self.fa[y]
            if not self.isroot(y):
                if (self.ch[z][0] == y) ^ (self.ch[y][0] == x):
                    self.rotate(x)
                else:
                    self.rotate(y)
            self.rotate(x)
        self.pushup(x)

    def access(self, x):
        last = 0
        while x:
            self.splay(x)
            self.ch[x][1] = last
            self.pushup(x)
            last = x
            x = self.fa[x]

    def makeroot(self, x):
        self.access(x)
        self.splay(x)
        self.pushrev(x)

    def find_root(self, x):
        self.access(x)
        self.splay(x)
        while self.ch[x][0]:
            self.pushdown(x)
            x = self.ch[x][0]
        self.splay(x)
        return x

    def split(self, u, v):
        self.makeroot(u)
        self.access(v)
        self.splay(v)

    def link(self, u, v):
        self.makeroot(u)
        if self.find_root(v) != u:
            self.fa[u] = v

    def cut(self, u, v):
        self.makeroot(u)
        if self.find_root(v) == u and self.fa[v] == u and self.ch[v][0] == 0:
            self.ch[u][1] = 0
            self.fa[v] = 0
            self.pushup(u)


def main():
    n, m = map(int, input().split())
    lct = LCT(n)
    arr = list(map(int, input().split()))
    for i in range(1, n + 1):
        lct.val[i] = arr[i - 1]
        lct.sum[i] = arr[i - 1]

    for _ in range(m):
        op, u, v = map(int, input().split())
        if op == 0:            # 查询路径异或和
            lct.split(u, v)
            print(lct.sum[v])
        elif op == 1:          # 连接
            lct.link(u, v)
        elif op == 2:          # 断开
            lct.cut(u, v)
        else:                  # 修改单点权值
            lct.splay(u)
            lct.val[u] = v
            lct.pushup(u)


if __name__ == "__main__":
    main()

6. 如何测试你的代码？

你可以用下面的简单测试样例来验证正确性：

输入：

5 7
1 2 3 4 5
0 1 3
1 1 2
1 2 3
0 1 3
2 2 3
0 1 3
3 1 10
0 1 3

解释：

  • 5个节点，7个操作。
  • 初始节点权值：1,2,3,4,5。
  • 操作0：查询1到3路径异或和（此时没有边，不连通，split 不会出错但 sum 可能只是1和3各自异或？注意 split 会换根，不连通时结果无意义，实际题目会保证操作合法。但这里只是演示，建议在合法时使用。）
  • 操作1：连边1-2。
  • 操作1：连边2-3。
  • 操作0：查询1到3路径异或和 → 1^2^3 = 0。
  • 操作2：断开2-3。
  • 操作0：查询1到3路径 → 1^2 = 3（注意此时1到3不连通，但LCT不会报错，返回的是以1为根到3的路径？实际上不连通时 split 仍会提取路径，但路径上只有1和3？严格来说不连通时路径不存在，实际使用应确保连通。这里仅作测试，结果可能不准确。）
  • 操作3：修改节点1的权值为10。
  • 操作0：查询1到3路径 → 10^2 = 8。

注意：LCT的 split 在两点不连通时仍会执行 makeroot(u) 和 access(v)，但此时v的根不是u，所以路径上可能只有u或v，或者包含中间的虚边节点？实际上，如果u和v不在同一棵树，access(v) 会把v到它自己树的根的路径打通，但u不在那条路径上。所以结果是没有意义的。在实际题目中，查询和连边/断边操作会保证合法性，或者你需要先判断连通性。

7. 常见考试 / 竞赛题型

  • 动态连通性：判断两个点是否连通（用 find_root）。
  • 路径信息查询：最大值、最小值、和、异或和等。
  • 最小生成树动态维护（如维护边权，用LCT维护最大边权，支持加边和删边）。
  • 树上操作：子树信息？LCT不擅长子树，因为树根会变。子树查询通常用树剖或可持久化。

8. 总结与扩展指引

LCT是一把瑞士军刀，能处理各种动态树问题。它的核心就是“Splay + 虚实变换”。记住几个关键口诀：

  • access 打通到根的路。
  • makeroot 先 access 再 splay 再翻转。
  • link 和 cut 前都先 makeroot(u)，再判断是否合法。

掌握了LCT，你还可以进一步学习：

  • 可持久化LCT（更深奥）
  • LCT维护边权（将边权转化为点权）
  • Euler Tour Tree（ETT），另一种动态树方案
  • 树链剖分（静态版）对比理解

现在，你已经学会了让树木自由生长的方法！快去试试吧。

例题精讲

1单选题

在动态树（Link-Cut Tree）中，access(x) 操作的主要目的是什么？

A将节点 x 到其所在树的根路径上的所有边变为实边，并使得 x 成为该路径的最后一个节点
B将节点 x 旋转到其所在 Splay 树的根
C将节点 x 与它的父节点连接起来，形成一条实边
D将节点 x 的子树全部变成实边路径
2判断题

在 Link-Cut Tree 中，makeroot(x) 操作可以通过先 access(x) 再 splay(x)，最后翻转 x 所在的 Splay 树来实现。

3单选题

对于一棵有 n 个节点的动态树，使用 Link-Cut Tree 进行 m 次操作（包含 link、cut、路径查询等），在均摊意义下，每次操作的时间复杂度是？

AO(log n)
BO(n)
CO(log^2 n)
DO(1)
4填空题
以下是 Link-Cut Tree 中 splay 操作的部分实现，请补全代码。假设已有函数 isroot(x) 判断 x 是否为所在 Splay 树的根，pushdown(x) 下传标记，rotate(x) 进行单次旋转。

void splay(int x) {
    stack<int> st;
    for (int y = x; !isroot(y); y = fa[y]) st.push(y);
    st.push(x);
    while (!st.empty()) { pushdown(st.top()); st.pop(); }
    while (___①___) {
        int y = fa[x], z = fa[y];
        if (!isroot(y)) {
            if ((___②___) == (___③___)) rotate(y);
            else rotate(x);
        }
        rotate(x);
    }
}

请将 ①、②、③ 处填写正确，使函数完整。
5填空题
下面是 Link-Cut Tree 中 link(x, y) 操作的代码，其功能是将节点 x 和 y 之间连一条边（假设 x 和 y 不在同一棵树中）。请补全缺失的两处（每处一个函数调用）。

void link(int x, int y) {
    makeroot(x);
    if (___①___ != y) {
        ___②___;
    }
}

已知 findroot(x) 返回 x 所在树的根节点，且已有 makeroot 和 access 等函数。请填写 ① 和 ② 处的完整表达式。