一、算法概述
动态树（Dynamic Tree）问题是指：维护一个会随时变化的森林，每个结点有权值，需要支持任意两个结点之间的连通性查询、边连接、边删除，以及对路径上的结点进行求和、求最大/最小值、修改等操作。1982 年 Sleator 和 Tarjan 提出的 Link-Cut Tree（以下简称 LCT）是第一个能够在均摊 O(log n) 时间内完成所有这些操作的经典数据结构，它的核心思想是把树形结构拆分成”实边”和”虚边”，并通过一系列精巧的旋转、暴露（expose）操作把任意结点到根的路径转换成”实路径”以便直接访问。
LCT 的难度远高于线段树、平衡树等普通数据结构。它需要熟练掌握 splay 树 作为底层容器，并且需要理解”路径偏好（path parent）”与”虚实边（preferred child / virtual child）”的区别。但一旦掌握，LCT 就能轻松处理一类”动态连通 + 路径维护”问题，比如动态最小生成树、动态最大流（部分实现）、网络割点处理等。
本文将系统讲解其设计原理，给出一个生产可用的 Java 实现，并展示 main 方法中的常见操作。
二、算法原理
2.1 数据结构概览
LCT 由若干棵 splay 树 组成。每一棵 splay 树表示一个”实路径”（preferred path）。整个森林被划分为若干条实路径，每条实路径用一棵 splay 树维护；不同实路径之间通过 虚边 连接，但不进入同一棵 splay 树。
对于结点 x：
– left[x], right[x]：splay 树中的左右子结点；
– parent[x]：父结点（在 splay 树中是父结点，在森林中可能是虚边的”路径父亲”）；
– reverse[x]：懒翻转标记，表示以 x 为根的子树需要翻转（用于路径反向）；
– value[x]：结点权值；
– sum[x], max[x]：以 x 为根的 splay 子树对应的聚合信息。
关键的概念是”expose(x)“，也常写作 access(x)，它把结点 x 到根结点（所在实路径树的根）之间的路径变成一条实路径，并把 x 设为该 splay 树的根。这是 LCT 一切高级操作的基础。
2.2 核心操作
2.2.1 isRoot(x)
判断 x 是否是其所在 splay 树的根。在 LCT 中，splay 树的根与 splay 树的 splay 操作后的根不同：只有在父结点的左右子都不指向 x 时，x 才是该 splay 树的根。这是 LCT 实现的关键判别条件。
2.2.2 pushUp(x)
维护 x 为根的 splay 子树信息（求和、最大值等）。具体取决于需要支持的查询类型。
2.2.3 pushDown(x)
下推 reverse 标记。reverse 会让左右子树交换，sum 不变但顺序需要翻；如果维护最大最小值则可能变化。
2.2.4 rotate(x)
标准的 splay 树旋转。需要先 pushDown 父结点链上的所有标记，再旋转。
2.2.5 splay(x)
把 x 通过一系列旋转提升到所在 splay 树的根。在 LCT 中，splay(x) 只会 把 x 提升到所在实路径对应的 splay 树的根，而不会跨越虚边。
2.2.6 access(x)
access(x):
last = null
while x != null:
splay(x)
right[x] = last
pushUp(x)
last = x
x = parent[x] // 跨过虚边
这一步把从 x 到根的路径变成了实路径，且 x 成为该 splay 树的根。
2.2.7 makeRoot(x)
makeRoot(x):
access(x)
splay(x)
toggle reverse[x]
把 x 设为所在树的根。access 之后 x 已经是 splay 树的根，再做懒翻转即可。
2.2.8 findRoot(x)
findRoot(x):
access(x)
splay(x)
pushDown(x)
while left[x] != null:
pushDown(x)
x = left[x]
splay(x)
return x
返回 x 所在树的根（最左侧结点）。
2.2.9 split(x, y)
把 x -> y 这条路径变成单独的实路径，方法是先 makeRoot(x)，再 access(y)，再 splay(y)。此时 y 所在 splay 树恰好对应 x -> y 的路径。
2.2.10 link(x, y)
先 makeRoot(x)，如果 findRoot(y) != x，则把 parent[x] = y，即连一条虚边。
2.2.11 cut(x, y)
makeRoot(x); access(y); splay(y)。如果 left[y] == x && right[x] == null，说明它们在同一条实路径上且中间没有其他点，此时 parent[x] = null; left[y] = null; pushUp(y)。
2.3 复杂度分析
每个 access 都会沿着路径把所有子路径变成实路径；总次数均摊后每个虚边只会被切换有限次，因此所有操作均摊为 O(log n)。整个 LCT 的时间复杂度是 均摊 O(log n)，空间复杂度是 O(n)。
三、Java 实现
下面给出一个支持”边权求和 + 边权修改 + 连通性判断 + 动态加边/删边”的完整 LCT 实现。我们将结点权值（这里直接用结点权值，便于后续扩展为边权：通过把边权下放到子结点即可）。
import java.util.Scanner;
/**
* Link-Cut Tree（LCT）—— 动态森林维护 + 路径聚合
*
* 支持：
* 1. 连通性判断：findRoot(x) == findRoot(y)
* 2. 路径求和 / 最大值
* 3. 路径翻转：makeRoot
* 4. 动态加边 link(x, y)
* 5. 动态删边 cut(x, y)
*
* 实现要点：
* - 底层使用 splay 树
* - 虚实边分离：实路径用一棵 splay 树维护，不同实路径之间靠虚边连接
* - access(x) 是核心操作，把 x 到根的路径变成实路径
*
* 复杂度：均摊 O(log n) 每操作
*/
public class LinkCutTree {
/** 结点数量（1-indexed） */
private final int n;
/** 左子结点 */
private final int[] ch = new int[4 * 100005 * 2];
/** 右子结点 */
private final int[] right = new int[ch.length];
/** 父结点 */
private final int[] parent = new int[ch.length];
/** 翻转懒标记 */
private final boolean[] reverse = new boolean[ch.length];
/** 结点权值 */
private final int[] value = new int[ch.length];
/** 子树权值和 */
private final long[] sum = new long[ch.length];
/** 子树最大权值 */
private final int[] max = new int[ch.length];
public LinkCutTree(int n) {
this.n = n;
for (int i = 1; i <= n; i++) {
value[i] = 0;
sum[i] = 0;
max[i] = Integer.MIN_VALUE;
}
}
/** 判断 x 是否是所在 splay 树的根 */
private boolean isRoot(int x) {
int p = parent[x];
return (ch[p] != x) && (right[p] != x);
}
/** 维护 x 的聚合信息 */
private void pushUp(int x) {
sum[x] = sum[ch[x]] + sum[right[x]] + value[x];
max[x] = value[x];
if (ch[x] != 0) max[x] = Math.max(max[x], max[ch[x]]);
if (right[x] != 0) max[x] = Math.max(max[x], max[right[x]]);
}
/** 下推翻转懒标记 */
private void pushDown(int x) {
if (reverse[x]) {
int l = ch[x], r = right[x];
// 交换左右子树
int tmp = ch[x]; ch[x] = right[x]; right[x] = tmp;
if (l != 0) reverse[l] = !reverse[l];
if (r != 0) reverse[r] = !reverse[r];
reverse[x] = false;
}
}
/** 准备旋转：将 x 到根路径上的懒标记全部下推 */
private void pushDownPath(int x) {
if (!isRoot(x)) pushDownPath(parent[x]);
pushDown(x);
}
/** splay 旋转 */
private void rotate(int x) {
int p = parent[x];
int g = parent[p];
// 子结点身份
if (!isRoot(p)) {
if (ch[g] == p) ch[g] = x;
else if (right[g] == p) right[g] = x;
}
parent[x] = g;
// 旋转方向：左旋还是右旋
if (ch[p] == x) {
// 右旋
int b = right[x];
right[x] = p;
parent[p] = x;
ch[p] = b;
if (b != 0) parent[b] = p;
} else {
// 左旋
int b = ch[x];
ch[x] = p;
parent[p] = x;
right[p] = b;
if (b != 0) parent[b] = p;
}
pushUp(p);
pushUp(x);
}
/** 把 x 提升到所在 splay 树的根 */
private void splay(int x) {
pushDownPath(x);
while (!isRoot(x)) {
int p = parent[x];
if (!isRoot(p)) {
int g = parent[p];
// zig-zig 或 zig-zag
if ((ch[g] == p) ^ (ch[p] == x)) {
rotate(x);
} else {
rotate(p);
}
}
rotate(x);
}
}
/** access(x)：把 x 到根的路径变成实路径 */
public void access(int x) {
int last = 0;
for (int y = x; y != 0; y = parent[y]) {
splay(y);
right[y] = last;
pushUp(y);
last = y;
}
}
/** makeRoot(x)：把 x 设为所在树的根 */
public void makeRoot(int x) {
access(x);
splay(x);
reverse[x] = !reverse[x];
}
/** 找到 x 所在树的根（最左结点） */
public int findRoot(int x) {
access(x);
splay(x);
pushDown(x);
while (ch[x] != 0) {
x = ch[x];
pushDown(x);
}
splay(x);
return x;
}
/** split(x, y)：把 x 到 y 的路径变成实路径 */
public void split(int x, int y) {
makeRoot(x);
access(y);
splay(y);
}
/** 路径 x -> y 的元素之和 */
public long pathSum(int x, int y) {
split(x, y);
return sum[y];
}
/** 路径 x -> y 的最大值 */
public int pathMax(int x, int y) {
split(x, y);
return max[y];
}
/** 修改结点 x 的权值为 v */
public void update(int x, int v) {
access(x);
splay(x);
value[x] = v;
pushUp(x);
}
/** 连接边 (x, y)：先 makeRoot(x)，再判断是否连通，最后连虚边 */
public void link(int x, int y) {
makeRoot(x);
if (findRoot(y) != x) {
parent[x] = y;
}
}
/** 删除边 (x, y) */
public void cut(int x, int y) {
makeRoot(x);
access(y);
splay(y);
// 检查是否直接相邻：x 是 y 的最左孩子，且 x 没有右孩子
if (ch[y] == x && right[x] == 0) {
ch[y] = 0;
parent[x] = 0;
pushUp(y);
}
}
/** 判断 x 与 y 是否在同一棵树中 */
public boolean connected(int x, int y) {
return findRoot(x) == findRoot(y);
}
// ================== 演示入口 ==================
public static void main(String[] args) {
LinkCutTree lct = new LinkCutTree(10);
// 初始化结点权值
for (int i = 1; i <= 10; i++) {
lct.update(i, i);
}
// 连成一棵树
lct.link(1, 2);
lct.link(2, 3);
lct.link(3, 4);
lct.link(2, 5);
lct.link(5, 6);
// 查询 1 -> 6 路径和
System.out.println("路径 1->6 的和：" + lct.pathSum(1, 6)); // 1+2+5+6=14
// 修改结点 5 的值为 100
lct.update(5, 100);
System.out.println("修改后路径 1->6 的和：" + lct.pathSum(1, 6)); // 1+2+100+6=109
// 删除边 (2,5)
lct.cut(2, 5);
System.out.println("删除边 2-5 后 1 与 6 是否连通：" + lct.connected(1, 6)); // false
System.out.println("删除边 2-5 后 5 与 6 是否连通：" + lct.connected(5, 6)); // true
}
}
四、复杂度分析
4.1 时间复杂度
- access(x)：每次会把一条实路径切换为虚路径；切换次数均摊后总代价为 O(log n)。
- makeRoot / findRoot / split：每次只调用常数次 access，因此也是 O(log n)。
- link / cut：调用
makeRoot+ 判连通 + 修改虚边，因此 O(log n)。 - pathSum / pathMax / pathMin：先
split再读根信息，O(log n)。 - update：access + splay 后修改值，O(log n)。
整体所有操作都是 均摊 O(log n)。
4.2 空间复杂度
每个结点固定大小的数组（约 6 个 int + 1 个 boolean + 1 个 long），所以 O(n)。对于 n = 1e5 的规模，内存占用约为 1-2 MB，是非常经济的。
4.3 注意点
- LCT 是 均摊 O(log n)，不是严格 O(log n)；在最坏情况下可能退化为 O(n)；
- 必须保证父结点引用在 splay 时被正确维护，否则会破坏森林结构；
- 路径聚合一定要先
split，否则会读到错误的子树。
五、应用场景
5.1 动态最小生成树
经典的”动态 MST”问题：维护一个带权的森林，支持加边（更新 MST）、删边（重新求解）。可以用 LCT 直接维护 MST 上的最大边权 + 替换，复杂度 O(log n) 每操作。
5.2 网络连通性
动态网络（路由器增删）中查询”两个终端是否仍然连通”，或”网络最大瓶颈”等。LCT 的 findRoot 与 pathMax 组合直接给出答案。
5.3 动态树剖
在某些题目中，我们需要对 子树 进行操作（如子树求和）。LCT 本身不支持”以父为根的子树聚合”，但可以通过 Euler Tour Tree（用 LCT 维护欧拉序）来实现。这个套路在处理”动态树 + 子树修改”问题时非常常见。
5.4 替代品与权衡
- Euler Tour Tree（ETT）：可以处理子树操作，但不支持路径反转；
- Top Tree：比 LCT 更强大，支持子树 + 路径双重操作，但实现复杂；
- Heavy-Light Decomposition + Segment Tree：仅支持静态树，但代码简单常数小。
在实际竞赛中，能用 HLF 就不用 LCT，因为 LCT 的常数非常大；但只要遇到动态操作，LCT 是首选。
六、总结
Link-Cut Tree 是处理动态森林连通性与路径维护问题的强大工具。它建立在 splay 树之上，借助”实路径/虚边”的精巧设计将森林中的任意路径转换为可操作的 splay 树。理解 LCT 的关键是掌握 access + makeRoot + splay 这三个核心操作的几何含义。在竞赛中，凡是遇到”动态加边/删边 + 路径聚合”的问题，都应该首先想到 LCT。
掌握 LCT 需要的不仅是”代码背过”，更是对虚实边切换的”画面感”——这需要大量的题目训练。本文给的代码是一个最小可运行版本，建议读者在此基础上扩展出区间修改、点权下放等更复杂的功能，以应对更高难度的题目。
