动态森林问题

能力边界 ​

路径聚合和子树聚合并不自动等价。Link-cut tree 擅长换根后的路径；Euler-tour tree 把整分量表示为循环序列；要把指定根下的子树定位成区间，还需相应的进入／退出标记和边界维护。加入非树边后 represented object 不再是森林，须由外层动态图算法选择生成森林并管理候选替代边。

路径最大值需规定权在边还是点上，以及空路径的聚合单位元。复杂度则按接口注明最坏界或摊还界。

Evert 改变父子方向，但保持无向路径的边集合，因此路径最大值不变。子树由根的方向决定，换根后会改变；支持路径聚合的结构还需额外设计才能维护子树摘要。

状态轨迹 ​

初始有三棵单点树。执行 link$(1,2,w=4)$、link$(2,3,w=7)$ 后，connected$(1,3)$ 为真，path-max$(1,3)=7$。再次 link$(1,3)$ 会成环，违反 link 的前提。每步森林的边数始终等于节点数减去分量数。

先以 1 为根，subtree$(2)=\{2,3\}$。执行 evert$(3)$ 后，subtree$(2)=\{1,2\}$，而 path-max$(1,3)$ 仍为 7。随后 cut$(2,3)$，1 与 3 才变得不连通。这个轨迹区分了换根造成的朝向变化和删边造成的连通性变化。

三类实现对应不同的聚合接口。Link–Cut Tree理路Link–Cut TreeLink-cut tree以 preferred-path 分解和辅助伸展树维护动态森林，在对数摊还时间内支持换根、连边、断边与路径聚合。把 preferred path 表示为辅助伸展树，适合 link、cut、evert 与路径聚合；Euler Tour Tree理路Euler Tour TreeEuler tour tree · ET-tree · 动态 Euler Tour Tree将无向树的 Euler 环游维护为可 split、join 的平衡序列，以支持动态森林的换根、连边、断边、连通性和分量聚合。把每棵树编码成可分裂合并的 Euler 序列，直接支持连通性和分量摘要；支持有根子树时须另行维护区间语义；Top Tree理路Top TreeTop tree · Top-tree dynamic forest把动态树递归分解为边界顶点至多两个的 cluster，并以 join、split 与 expose 在对数层级中维护路径及整树摘要。以至多两个边界点的 cluster 分层合并，更对称地承载路径、直径和树上动态规划。选择结构前必须先固定查询是路径型、子树型还是 cluster 型。

聚合维护 ​

按边取权时，空路径的最大值单位元可取 $-\mathrm{\infty }$，反转路径不改变结果；若为非交换字符串拼接，evert 还须维护正反两个摘要。对边权最大值，lazy path-add 在覆盖目标路径的辅助树节点上同步更新边值、非空路径最大值摘要和 tag；下推时再把增量传给孩子。点权查询即使两端相同也含一个点，不能与空边路径混用。所报数据结构成本通常假设摘要和标记占常数字、合并与施加标记为常数时间；输出整条路径或拼出长字符串时另计输出成本。