Link–Cut Tree | Codeboy's Blog

形式陈述

三层对象不能混为一棵树

Link–Cut Tree 为动态森林问题维护一片 represented forest：这是用户语义中的动态有根森林。结构另外根据最近的 access 选择 preferred edges；每个顶点至多有一条指向 preferred child 的边，因此 preferred edges 把 represented forest 分成若干条 preferred paths。每条路径再由一棵辅助伸展树按 represented depth 的顺序保存。

所以同时存在三种关系：

represented parent：森林中真正的父子关系；
preferred/path-parent：一条辅助路径与上一条路径的连接；
auxiliary parent：伸展树旋转所维护的父指针。

Splay 旋转只能改变 auxiliary parent 和路径表示，不能改写 represented forest。把这三种父指针视为一个字段而不维护相应语义，是 Link–Cut 实现最危险的错误来源。

接口与复杂度

对 $n$ 个顶点，经典 Link–Cut Tree 支持：

$\operatorname{access}(v)$ ：把 represented root 到 $v$ 的路径变成一条 preferred path；
$\operatorname{makeRoot}(v)$ ：把 $v$ 变成所在 represented tree 的根；
$\operatorname{findRoot}(v)$ ：返回 represented root；
$\operatorname{link}(u,v)$ ：仅当 $u,v$ 在不同树中时加入边；
$\operatorname{cut}(u,v)$ ：删除已存在的 represented edge；
$\operatorname{pathQuery}(u,v)$ ：在端点连通时聚合简单路径 $u\leadsto v$ ，否则返回无路径。

预处理孤立顶点为 $O(n)$ ，空间 $O(n)$ 。每项操作均为最坏可能线性、但摊还 $O(\log(n+1))$ ；长度为 $m$ 的合法操作序列总时间为 $O((n+m)\log(n+1))$ 。这里假设固定大小摘要及其合并、lazy 标记操作均为常数成本。保证来自伸展树及 preferred-path 的摊还分析；实际展开长字符串或输出整条路径还须另计成本。

access 如何改写 preferred paths

概念上， $\operatorname{access}(v)$ 从 $v$ 沿 path-parent 逐段走向 represented root。维护变量 last，初始为空；对当前辅助树顶点 $y$ ：

splay $(y)$ ，使 $y$ 成为当前辅助树根；
原右子树表示 $y$ 下方旧的 preferred 后缀，把它断开为 virtual 连接；
把 last 接为 $y$ 的右子树，使刚访问过的下一段成为新 preferred 后缀；
更新聚合，令 last= $y$ ，继续到上一条 preferred path。

最后再 splay $(v)$ 。此时包含 $v$ 的辅助树按中序保存 represented root 到 $v$ 的路径， $v$ 位于这条序的末端并成为辅助根。access 改变了哪些边是 preferred，却没有 link 或 cut 任何 represented edge。

换根、连边、断边与路径摘要

$\operatorname{makeRoot}(v)$ 先 access $(v)$ ，再对整条暴露路径施加 lazy reverse。反转后 represented 路径方向颠倒， $v$ 成为新根。Reverse 标记必须交换左右孩子；若路径摘要的运算不交换，还要交换“正向摘要”和“反向摘要”。

检查 $u,v$ 连通后，要查询 $u\leadsto v$ ，执行

\operatorname{makeRoot}(u);\qquad \operatorname{access}(v).

此时 $v$ 的辅助树恰按路径 $u\leadsto v$ 排列，根部摘要就是答案。若节点值属于幺半群 $(M,\circ,e)$ ，结合律足以在旋转后重算摘要；不要求可逆，也不要求交换。这套操作把 represented root 改成了 $u$ ；若外部查询接口承诺保持原根，应先保存 findRoot $(u)$ ，读完摘要后再 makeRoot 回原根。增加常数次操作不改变摊还界。

$\operatorname{link}(u,v)$ 先 makeRoot $(u)$ 并检查 findRoot $(v)\ne u$ ，再把 $u$ 的 represented parent 设为 $v$ 。若省略连通性检查，就会在森林中制造圈。删除边 $(u,v)$ 时，先 makeRoot $(u)$ 、access $(v)$ ；若两点确为相邻 represented 顶点，暴露序列中该连接可被唯一断开。仅按“某点当前是另一个点的 splay 左孩子”而不核对相邻关系，可能误删整段路径。

直觉

为什么是对数摊还

对辅助伸展树使用 access lemma 的秩势

\Phi=\sum_x\log s(x),

其中 $s(x)$ 按 Link–Cut 的虚实子树权重定义，使 splay 旋转的实际成本由秩差支付。一次 access 虽可能跨过许多 preferred paths，但各段 splay 的秩项沿 represented root– $v$ 路径望远镜相消；把 preferred edge 改为 virtual 或反向接入造成的剩余势差，也由端点子树权重的对数变化控制。整次 access 的摊还成本因此为 $O(\log(n+1))$ ，而不是“经过的 preferred path 数天然总是 $O(\log(n+1))$ ”。

这一区别很重要：单次 access 可以改变许多 preferred children，单棵辅助树也可以暂时很高。保证来自整串操作上的势能，而非每个时刻存在一棵高度对数的平衡树。

Link–Cut Tree 中 represented tree、preferred paths 与 access 后 auxiliary tree 的对比 — Link–Cut Tree 三层关系

例子与边界

具体例子：暴露任意两点路径

设 represented tree 含路径 $a-b-c-d$ ，另有边 $c-e$ 。即使当前 preferred paths 因过去查询被分成 $a-b$ 、 $c-e$ 和单点 $d$ ，执行 makeRoot $(b)$ ；access $(e)$ 后，辅助树仍会重新拼成按 $b-c-e$ 排列的路径。边权可以用独立的边节点表示：每条 represented edge 在辅助表示中细分为“端点—边节点—端点”，只让边节点贡献权值，原顶点贡献最大值单位元。换根时权值始终附着于同一条边，根摘要就是路径最大边；森林中至多 $n-1$ 个边节点，空间仍为 $O(n)$ 。这种表示避免把边值固定放在旧的较深端点、换根后却忘记搬移的问题。

随后 cut $(c,e)$ 会让 $e$ 成为独立分量，而 $a,b,c,d$ 仍相连；splay 内部旋转的形状与 represented forest 的两个分量无关。

失败边界与近邻结构

原生 Link–Cut Tree 把路径变成辅助树中的连续序列，因此路径和、最大值、仿射复合等最自然。整棵 represented subtree 的顶点散落在多条 preferred paths 和 virtual children 中；要支持动态子树聚合必须额外维护 virtual contribution，并处理 access 时贡献进出，不能从路径摘要自动得到。

非交换运算必须保留方向：字符串拼接或矩阵乘法在 $u\leadsto v$ 与 $v\leadsto u$ 上结果不同，lazy reverse 只交换孩子而不交换正反摘要会静默产生错误。Euler Tour Tree更适合连通分量和某些子树/分量聚合，二者能力互补，不是不同代码风格的同一结构。

推论与应用

Link–Cut Tree 适合动态最小生成森林中的 path-max、树上路径和与换根查询，也能作为更大动态图算法的 represented-forest 层。若核心查询是整分量或子树聚合，Euler Tour Tree 往往更自然；两者的外部森林接口相似，连续化的对象却不同。

参考资料

Daniel D. Sleator and Robert E. Tarjan, “A Data Structure for Dynamic Trees,” Journal of Computer and System Sciences 26(3), 1983, 362–391.
Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983, dynamic trees chapter.
Erik D. Demaine, MIT 6.851 Advanced Data Structures, lecture notes on dynamic trees, accessed 2026.

形式陈述 ​

三层对象不能混为一棵树 ​

接口与复杂度 ​

access 如何改写 preferred paths ​

换根、连边、断边与路径摘要 ​

为什么是对数摊还 ​

具体例子：暴露任意两点路径 ​

失败边界与近邻结构 ​

反向链接