Link–Cut Tree

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

Link–Cut Tree 维护的是一片 represented forest：这是用户语义中的动态有根森林。结构另外根据最近的 access 选择 preferred edges；每个顶点至多有一条指向 preferred child 的边，因此 preferred edges 把 represented forest 分成若干条 preferred paths。每条路径再由一棵辅助 伸展树公理库伸展树splay tree · 伸展树每次访问后把目标旋至根，并以势能获得序列敏感摊还界的自调整搜索树。按 represented depth 的顺序保存。

所以同时存在三种关系：

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

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

接口与复杂度 ​

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

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

预处理孤立顶点为 $O(n)$，空间 $O(n)$。每项操作均为最坏可能线性、但摊还 $O(\log n)$；长度为 $m$ 的合法操作序列总时间为 $O((n+m)\log n)$。保证来自伸展树的摊还分析，不应写成单次最坏 $O(\log n)$。

access 如何改写 preferred paths ​

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

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

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

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

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

要查询 $u⇝v$，执行

$$\mathrm{makeRoot}(u);\mathrm{access}(v).$$

此时 $v$ 的辅助树恰按路径 $u⇝v$ 排列，根部摘要就是答案。若节点值属于 幺半群公理库幺半群Monoid具有双侧单位元的半群。 $(M,\circ ,e)$，结合律足以在旋转后重算摘要；不要求可逆，也不要求交换。

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

为什么是对数摊还 ​

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

$$\mathrm{\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)$，而不是“经过的 preferred path 数天然总是 $O(\log n)$”。

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

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

设 represented tree 含路径 $a-b-c-d$，另有边 $c-e$。即使当前 preferred paths 因过去查询被分成 $a-b$、$c-e$ 和单点 $d$，执行 makeRoot$(b)$；access$(e)$ 后，辅助树仍会重新拼成按 $b-c-e$ 排列的路径。若每条边存权值并维护最大值幺半群，根摘要就是这条路径的最大边。

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

失败边界与近邻结构 ​

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

非交换运算必须保留方向：字符串拼接或矩阵乘法在 $u⇝v$ 与 $v⇝u$ 上结果不同，lazy reverse 只交换孩子而不交换正反摘要会静默产生错误。Euler Tour Tree公理库Euler Tour TreeEuler tour tree · ET-tree · 动态 Euler Tour Tree将无向树的 Euler 环游维护为可 split、join 的平衡序列，以支持动态森林的换根、连边、断边、连通性和分量聚合。更适合连通分量和某些子树/分量聚合，二者能力互补，不是不同代码风格的同一结构。

参考资料

• 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, Advanced Data Structures, MIT 6.851 lecture notes, dynamic trees.