动态森林问题

抽象接口 ​

作为动态图模型公理库动态图算法模型Dynamic graph algorithm model统一图更新序列、查询接口、对手权限以及更新和查询保证。的受限接口，结构维护 represented forest，支持 link((u,v))、cut((e))、connected、find-root，可选 evert、path aggregate 与 subtree aggregate。Link 前必须验证端点属于不同树，否则会成环；cut 是按边还是按父子关系也须固定。

例如维护网络骨架上两点路径最大边：link 接入新边，cut 删除故障边，path-max 支持 MST 替换判断。辅助结构可能是 link-cut tree 或 Euler-tour tree，但它不改变外部森林。

能力边界 ​

路径聚合和子树聚合并不自动等价。Link-cut tree 擅长换根后的路径；Euler-tour tree把子树变连续区间。加入非树边后 represented object 不再是森林，须由外层动态图算法选择生成森林并管理候选替代边。

根是否固定会改变 subtree 语义。复杂度还须注明摊还/最坏及聚合运算是否可逆。

Link 的契约是两端根不同，cut 的边必须存在；否则 represented forest 不变量立刻失效。路径最大值需规定权在边还是点及聚合单位元。Evert 改变父子方向但不改变无向路径，subtree 语义却随根改变，所以支持 path aggregate 不能推出支持 subtree aggregate。

从三棵单点树开始，link$(1,2)$、link$(2,3)$ 后 path-max$(1,3)$ 聚合两条边；再次 link$(1,3)$ 必须拒绝，因为 roots 相同。Evert$(3)$ 后无向路径不变，原来以 1 为根的 subtree$(2)$ 却改变。这条轨迹直接区分路径与子树接口。

状态轨迹 ​

初始三棵单点树，link$(1,2,w=4)$、link$(2,3,w=7)$ 后 connected$(1,3)$ 为真、path-max$(1,3)=7$。再次 link$(1,3)$ 必须拒绝，因为 find-root 相同；cut$(2,3)$ 后答案变 false。每步 represented forest 的边数等于节点数减分量数。

Evert$(3)$ 把 3 设为根，路径边集合不变，所以 path-max 不变；以原根定义的 subtree$(2)$ 则从包含 3 变成包含 1。任何支持 subtree 的结构必须把根参数或当前朝向纳入状态。

聚合维护 ​

路径聚合若为最大值，单位元是 $-\mathrm{\infty }$，反转路径不改变结果；若为非交换字符串拼接，evert 还须维护正反两个摘要。Lazy path-add 要同步更新节点值、路径最大和 tag，不能只改根辅助节点。

Link-cut tree把 preferred paths 存为辅助 splay，擅长路径；Euler-tour tree把每棵树的 tour 存为可 split/join 序列，擅长子树/连通。接口重叠不代表摘要能力相同。

参考资料

• Sleator, Tarjan, “A Data Structure for Dynamic Trees,” JCSS, 1983.
• Henzinger, King, dynamic graph framework, STOC 1995.