Top Tree

Cluster 与边界 ​

在 represented forest 中，一个 cluster $C$ 是一组连通树边及其端点。若某顶点既接触 $C$ 内边又接触 $C$ 外边，或被当前 expose 指定为外部接口，就是 boundary vertex。Top Tree 只允许

$$|\partial C|\le 2.$$

一个边界的 cluster 常称 point cluster，两个边界的称 path cluster；单条树边是叶 cluster。Cluster 摘要只应依赖内部边、顶点值和边界身份，使父 cluster 能由两个孩子在常数时间合并。

Join、Split 与层级不变量 ​

若两个 edge-disjoint clusters 只共享一个顶点，且并集仍连通、边界不超过两个，就可 join 成父 cluster。共享顶点若不再接触外部边，会在父摘要中变成内部点；若并集产生三个外部接口，这次 join 非法。

Top-tree hierarchy 是一棵平衡二叉树：叶是 represented edges，内部节点记录一次合法 join，根表示整棵 represented tree。split 撤销一个 join。平衡不变量保证任意叶到 cluster 根的高度为 $O(\log n)$。

因此修改一条 represented edge 只需沿 $O(\log n)$ 个祖先重算摘要，正是局部增强公理库搜索树增强定理与方法Search-tree augmentation在搜索树节点维护可由局部子树摘要恢复的信息，并证明旋转后仍可常数更新。在 cluster 层级上的版本。

动态接口与保证 ​

link(u,v) 为不同树加入叶 cluster；cut(e) 删除已有叶；expose(u,v) 重排层级，使 $u,v$ 成为根 cluster 的两个边界，从而把路径 $u⇝v$ 暴露给根摘要。单点 expose 则只保留一个指定边界。

在标准确定性平衡实现中，link、cut 与 expose 各触发 $O(\log n)$ 次 split/join，若摘要合并为 $O(1)$，每项操作最坏 $O(\log n)$、空间 $O(n)$。若底层用自调整平衡器，保证可能改为摊还；实现必须注明选定版本。

动态直径真例 ​

对非负边权树，cluster 可保存：两个边界间距离；每个边界到 cluster 内最远顶点的距离；cluster 内部直径及其端点。Join 在共享边界 $x$ 处组合两个孩子时，父直径是

$$max\{diam(C_1),diam(C_2),fa{r}_{C_1}(x)+fa{r}_{C_2}(x)\}.$$

边界到最远点和边界间距离也由孩子常数项取最大或相加。这个摘要闭合于 join，所以整树根始终保存当前直径。

例如路径 $a-b-c$ 边权为 $2,5$，直径为 $7$。Link$(c,d,1)$ 后，只重算覆盖新边的对数个 clusters，根直径变为 $8$；再 cut$(b,c)$，两个根摘要分别给出分量 $a-b$ 的直径 $2$ 与 $c-d$ 的直径 $1$。

摘要合并的边界 ​

“可组合”不等于任意全局性质都能常数合并。摘要必须保留跨共享边界生成新候选所需的全部接口状态；若只存孩子内部直径而不存 far(x)，就无法计算跨孩子最长路。

负边权时空路径是否允许会影响直径单位元与“单点路径”约定。非交换路径摘要还要记录两个方向；Expose 交换边界次序时必须同步转换摘要。

与 Link–Cut Tree、ETT 的区分 ​

Link–Cut Tree公理库Link–Cut TreeLink-cut tree · 动态树以 preferred-path 分解和辅助伸展树维护动态森林，在对数摊还时间内支持换根、连边、断边与路径聚合。把 preferred path 存成辅助 splay，路径聚合直接，但整树/虚子树信息需额外维护。Euler Tour Tree公理库Euler Tour TreeEuler tour tree · ET-tree · 动态 Euler Tour Tree将无向树的 Euler 环游维护为可 split、join 的平衡序列，以支持动态森林的换根、连边、断边、连通性和分量聚合。把整棵分量表示为序列，擅长连通与分量聚合。

Top Tree 以边界不超过两个的 cluster 统一表达路径和整树摘要，代价是 join 类型、expose 重排和实现常数更复杂。三者都实现动态森林公理库动态森林问题Dynamic forest problem维护无环树族的 link、cut、连通、换根及路径或子树聚合接口。接口，却不是同一内部树的不同命名。

失败边界 ​

Link 前若不检查两端分量不同，会制造环，使 cluster 不再是树子图。Cut 若按端点而非边实例定位，在平行边外层模型中可能删错对象。

一个 represented 顶点可出现在多个 cluster 边界角色中，但每条 represented edge 只能属于一个叶；重复计入边会让距离和分量大小失真。Cluster 重排只改变辅助层级，绝不能改变 represented forest。

参考资料

• Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup, “Maintaining Information in Fully Dynamic Trees with Top Trees,” ACM Transactions on Algorithms 1(2), 2005.
• Daniel D. Sleator and Robert E. Tarjan, “A Data Structure for Dynamic Trees,” Journal of Computer and System Sciences 26(3), 1983.
• Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup, “Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity,” Journal of the ACM 48(4), 2001.