编程面试：如何用 Link-Cut Tree 维护动态森林？

题干与适用场景

给定一个动态森林，边会被加入或删除，节点带有整数值。需要支持 link(u,v)、cut(u,v)、路径最大值查询和路径加值。请说明 Link-Cut Tree 的表示、access、makeroot、惰性标记、正确性与复杂度。

Sleator 与 Tarjan 的动态树结构支持把两棵树连接和把一条边切开，每个操作达到摊销 O(log n)。面试重点是能否把“真实树路径”和“辅助 Splay 的首选路径”区分开，而不是背出一段模板代码。

面试官考察点

• 是否知道 Link-Cut Tree 维护的是 represented forest，并用辅助 Splay 保存 preferred path。
• 能否正确实现 isRoot、push、pull、旋转和 splay。
• 是否理解 access 如何把节点到根的路径改成 preferred path。
• 能否用 makeroot 的反转标记支持无根路径，并避免懒标记顺序错误。
• 是否在 link、cut 前验证连通性和边确实存在。
• 能否说明摊销 O(log n)，以及数组、递归深度和随机测试风险。

回答前需要澄清的问题

1. 结构保证始终是森林，还是可能出现环？Link-Cut Tree 不负责一般图的连通性维护。
2. 路径更新是加法、赋值还是同时需要最大/最小值？不同操作需要不同聚合与懒标记。
3. 节点值还是边值？若是边值，可把边映射为虚拟节点。
4. 操作是否需要持久化、并发，或只需单线程在线处理？
5. 输入是否包含重复 link、不存在的 cut 和自环？

30 秒回答框架

我会用每个节点一个辅助 Splay，ch 表示 Splay 子树，fa 表示辅助父节点或路径父节点。access 从节点向上遍历，逐步把右子树替换为已处理路径；makeroot 先 access 再翻转整棵辅助树。link 在确认不连通后 makeroot，再连接；cut makeroot(u)、access(v)，检查 v 的左子树是否正好是 u，再断开。每次修改前 push，修改后 pull；操作摊销 O(log n)。

分步骤深入解答

1. 表示两种树关系

辅助 Splay 的左右孩子描述 preferred path 上的顺序；fa 在节点是辅助根时不代表 Splay 父子，而代表 represented tree 中的路径父节点。因此 isRoot(x) 必须判断 x 是否不是父节点的左右孩子，不能只检查 fa[x] == 0。

2. 维护聚合和懒标记

对路径最大值，pull(x) 汇总自身值和两个 Splay 子树的最大值。路径加值可用 add 标记；路径反转用 rev 标记交换左右孩子。push(x) 必须先把 rev 传播，再传播 add，或在实现中明确两者可交换的代数关系。

pull(x): mx[x] = max(value[x], mx[ch[x][0]], mx[ch[x][1]])
applyAdd(x,d): value[x] += d; mx[x] += d; add[x] += d
applyRev(x): swap(ch[x][0], ch[x][1]); rev[x] ^= true

3. 实现 access

设 last = 0，从 x 向 fa[x] 走：先 splay(y)，把 y 的右孩子设为 last，pull(y)，再把 last 设为 y 并继续。循环结束后 splay 原始 x。这样 x 到 represented root 的路径被拆成一条 preferred path，x 的 Splay 顺序可用于路径聚合。

4. 实现 makeroot

makeroot(x) 执行 access(x)，随后给 x 打 rev 标记。此时 x 成为 represented tree 的根，后续 link(x,y) 才能把两棵树正确连接。不能直接物理递归翻转整棵 represented tree；反转只需要延迟到辅助 Splay。

5. 实现 link 与 cut

link(x,y) 先 makeroot(x)，确认 findroot(y) != x，再令 fa[x] = y。cut(x,y) 先 makeroot(x)、access(y)，此时若边存在，y 的左孩子应为 x 且 x 没有右孩子；断开 ch[y][0] 并清除其父指针。检查条件可避免切掉路径上的其他节点。

6. 查询和更新路径

split(x,y) 等价于 makeroot(x); access(y)，此时 y 的辅助 Splay 包含 x 到 y 的路径。读取 mx[y] 得到最大值；路径加值则对 y 应用 applyAdd。查询前后不需要恢复 preferred path，因为下一次 access 会重新整理它。

7. 复杂度和测试

Sleator–Tarjan 分析给出 link、cut、root、evert 等操作的摊销 O(log n)，空间为 O(n)。用小规模森林与朴素邻接表交叉测试：随机生成合法 link/cut，比较路径最大值和加值结果；额外覆盖单点、反复 makeroot、连续 access、非法 cut、所有值相等和负数。

高质量示范回答

我会把 fa 同时作为辅助父或路径父，靠 isRoot 区分，避免把 represented tree 当成一棵普通二叉树。每个 Splay 节点维护值、子树最大值、反转和加法标记。access 从目标向根整理 preferred path；makeroot 在 access 后打反转标记；split(x,y) 让 y 的 Splay 表示 x 到 y 的路径。

link 先 makeroot 并拒绝已连通节点；cut 先 makeroot/access，再确认 y 的左子树正好是 x 后断边。每次旋转前按祖先顺序 push，修改后 pull。理论上操作摊销 O(log n)、空间 O(n)，我会用朴素森林随机交叉测试路径聚合、非法操作和懒标记组合。

常见错误

• 用 fa[x] == 0 判断辅助根 → 路径父节点可能非零 → 用 isRoot 检查左右孩子关系。
• 忘记在旋转前 push 祖先 → rev 或 add 未传播，聚合错误 → 先收集祖先栈并反向 push。
• cut 不检查边 → 会切断路径中错误节点 → makeroot/access 后验证左子树结构。
• link 不检查连通性 → 形成环，结构不再是森林 → 先 findroot 判断。
• 把 access 后的 Splay 当作整棵 represented tree → 只能保证当前 preferred path → 通过下一次 access 重新组织。
• 只测查询不测更新 → 懒标记问题被隐藏 → 与朴素森林做随机路径加值交叉测试。

追问及应对

如何维护路径最小值或异或值？

替换 pull 的幺半群聚合即可；异或在反转时不受顺序影响，非交换聚合则必须确认路径方向和反转后的合并顺序。

如何把边权纳入路径查询？

把每条边拆成一个虚拟节点，虚拟节点值为边权，再用普通节点路径聚合；link/cut 时维护对应虚拟节点生命周期。

为什么 access 的旧右子树可以直接替换？

旧右子树仍通过 fa 保留 represented path 的父关系，只是不再是当前 preferred path。辅助 Splay 的孩子关系和路径父关系分离，替换不会丢失森林结构。

能否支持路径赋值？

可以增加赋值标记，并定义它覆盖旧 add、更新 value/mx，再按明确顺序传播 rev。关键是标记组合必须有可证明的优先级。

如何证明 findroot 正确？

对 x 执行 access 后不断 push 并沿最左孩子走到 Splay 最左节点；该节点对应 represented tree 根，再 splay 它以稳定后续操作。

什么时候不该使用 Link-Cut Tree？

若森林静态，可用 DFS/Euler Tour 或重链剖分；若是一般动态图连通性或需要并发、持久化，Link-Cut Tree 的维护边界和实现风险可能不合适。