动态森林问题

能力边界 ​

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

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

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

状态轨迹 ​

初始三棵单点树，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 的结构必须把根参数或当前朝向纳入状态。

三类实现对应不同的聚合接口。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，不能只改根辅助节点。

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