核心概述
Link-Cut Tree（LCT）基于 Splay 的动态树结构，支持在森林上在线 link/cut/makeRoot 及路径查询/修改，单次均摊 O(log N)。
原文引述
Description: Dynamic tree structure (Splay-based) supporting path queries/updates on a forest with link/cut/makeRoot operations. Time: Amortized O(log N) per operation
展开阐述
定义与背景
- 定义：LCT 将一片森林通过若干棵 Splay（辅助树）覆盖，借助 access 将任意根→x 的路径暴露为一条可操作的首链（偏右链），再结合翻转标记与 pushDown/pullUp 维护路径聚合信息，实现“动态树”上的路径操作。
- 背景与动机：与静态树方案（如 066-图论-重链剖分、068-图论-最近公共祖先）不同，LCT 允许在线地连边/断边/换根，并在此基础上进行路径聚合（sum/max/xor 等）。
典型适用场景：
- 在线维护动态森林连接关系与路径信息（如边权/点权的路径和/最大值/异或值）；
- 动态最小生成树、动态连通性、树上可并查询等需要频繁 link/cut 的问题。
接口/字段/数据结构（据常见实现）
- 主要操作
- makeRoot(x)：将 x 所在树换根为 x（通过翻转根→x 的首链）；
- link(u, v)：若 u、v 属于不同树，则连边 u–v；
- cut(u, v)：若边 u–v 存在，则删除该边；
- connected(u, v)：判断 u、v 是否在同一棵树；
- access(x)：依次把根→x 的路径“切下并接到”x 的右侧，使 x 所在 Splay 表示整条路径；
- queryPath(u, v) / updatePath(u, v, val)：先 makeRoot(u) 再 access(v)，对 v 的 Splay 进行查询或标记更新。
- 关键节点字段（每个节点一份）
- ch[2]：左右儿子（在辅助树中的指针）；
- fa：父指针（辅助树中父）；
- rev：懒翻转标记（用于路径反向/换根）；
- val：点权（或映射后的边权）；
- agg：聚合值（如路径和/最大值/异或等，按模板定义）；
- 维护例程
- isRoot(x)：判断 x 是否为其所在 Splay 的根（即不作为父的左右儿子）；
- pushDown(x)：下传翻转标记等懒标记；
- pullUp(x)：按 ch 与 val 重算聚合信息；
- rotate(x) / splay(x)：Splay 旋转与提升。
语义约定：
- 边权通常映射到较深端点的“点权位”（同 066-图论-重链剖分 的习惯）；
- queryPath 与 updatePath 在 makeRoot+access 后直接对 v 的 Splay 根执行。
核心流程/要点（access 序列 + 懒标记）
- access(x)
- 从 x 出发，沿“首链提升”逐段切下根→x 的路径，把每段接到当前首链的右侧；
- 最终 x 所在 Splay 表示整条根→x 的路径，便于聚合/修改；
- makeRoot(x)
- access(x) 后 splay(x)，对 x 打 rev 翻转标记，使原路径方向翻转，从而把 x 作为整棵树的“新根”；
- link(u, v)
- 若 connected(u, v) 为假：makeRoot(u)，再将 u 的 fa=v（或等价的 link 逻辑），完成连边；
- cut(u, v)
- makeRoot(u)，access(v) 并 splay(v)，此时 v 的左子树应为从 u 到 v 的整段路径；断开该边即可；
- query/update 路径
- makeRoot(u)，access(v) 后 splay(v)，对 v 的 Splay 根执行聚合查询或标记更新。
实现要点：
- 旋转前必须 pushDown 自上而下，保证结构与聚合值正确；
- pullUp 自底向上在旋转/修改后及时重算；
- rev 标记与左右儿子交换顺序必须一致，避免路径方向与聚合失配；
- connected 判定常用“找根”（通过 access + splay 把根提到顶部后向左一路走到最左端）来比较根是否相同。
复杂度与边界条件
- 复杂度：所有操作均摊 O(log N)（来自 Splay 的摊还分析）；
- 空间：O(N)；
- 边界与一致性：
- 重边/自环：应在调用端规避（link 前检查 connected(u, v)）；
- 多根森林：自然支持；每个连通分量一棵动态树；
- 子树聚合：标准 LCT 支持路径聚合；若需子树聚合，常见做法为扩展到 ETT（Euler Tour Tree）或在 LCT 上维护虚子树信息，难度较高；
- 点权/边权：若为边权，采用“映射到深端点”的存储与查询约定，避免二义性。
变体/扩展与关系
- 与 066-图论-重链剖分：HLD 更适合静态树的高效路径/子树操作；LCT 支持在线 link/cut；
- 与 068-图论-最近公共祖先 / 054-图论-二进制提升：LCA/倍增针对静态查询；动态连边需 LCT；
- 结合“可换根”的路径问题：makeroot + access 统一暴露路径语义；
- 维护函数拓展：agg 可扩展为 sum、max、xor、矩阵乘积等，但要求可在 Splay 的局部维护上封闭可合并。
正确性要点与不变式
- 首链暴露不变式：access(x) 后，x 所在 Splay 中序即为根→x 的路径；
- 懒标记与方向一致性：rev 下传必须交换左右儿子并对聚合方向敏感的字段做相应处理；
- 聚合闭包：pullUp 需要满足“左右子树聚合 + 自身 val = 节点 agg”的闭包与结合性；
- 无环性：link 前需确保 not connected(u, v)，否则会形成环破坏“森林”前提。
与相邻技术的对比与取舍建议
- 仅静态路径/子树：优先 066-图论-重链剖分；
- 需要在线 link/cut/换根：使用 LCT；
- 只求 LCA 或祖先跳跃：068-图论-最近公共祖先 / 054-图论-二进制提升 常数更小；
- 需要子树聚合：考虑 ETT 或 HLD；标准 LCT 以路径为主。