Euler Tour Tree

形式陈述 ​

表示不变量 ​

为实现动态森林问题理路动态森林问题Dynamic forest problem维护无环树族的连接、断开与连通查询，并按所选版本增加有根或聚合接口。的 link、cut 与连通查询，对 represented forest 中每棵无向树 $T$，把每条边 $\{u,v\}$ 变成两个有向出现 $(u,v)$ 与 $(v,u)$。从任意根开始沿每条有向边恰走一次，得到长度 $2|E(T)|$ 的循环 Euler tour。为使孤立顶点也有序列位置，并方便顶点值聚合，常再给每个顶点放一个自出现 marker，放置位置必须是环游正好访问该顶点之处。

每棵树的循环 tour 从任意位置切开，存入支持以下操作的动态序列容器：

叶按 tour 顺序排列，内部节点维护大小和幺半群理路幺半群Monoid具有双侧单位元的半群。摘要。以下时间界假设摘要占常数字且合并为常数时间；实际输出长序列时还须计输出成本。结构树只是序列容器；它的父子关系不是 represented tree 的父子关系。每个 represented 顶点或有向边保存指向其叶出现的句柄，以便在 $O(\log (n+1))$ 时间定位并切分。

选定实现下的复杂度 ​

一种实现使用隐式随机 Treap理路Treap 与随机优先级搜索树treap · randomized search tree同时满足键的搜索树序和独立随机优先级堆序的随机平衡树。：中序位置充当键序，split 按子树大小定位切分点，节点位移不需要逐个重写数值键；各出现节点的独立随机优先级在其生命周期内固定。对任意预先固定的合法操作序列，split/join 的期望时间为 $O(\log (n+1))$；若使用具有 join/split 保证的确定性平衡树理路平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。，可得到相应最坏 $O(\log (n+1))$。以下以 Treap 版本为例：

• 预处理与空间：$O(n)$；
• reroot、link、cut：期望 $O(\log (n+1))$；
• connected：比较两处 marker 所在序列根，期望 $O(\log (n+1))$；
• component aggregate：找到序列根后读取摘要，期望 $O(\log (n+1))$。

这里的期望来自随机优先级，而非输入图分布。若对手能观察优先级并自适应构造操作，需重新说明随机保证或改用确定性平衡序列。

reroot、link 与 cut ​

Euler tour 是循环序列，改变 represented root 只需旋转序列，并更新显式保存的根身份。若顶点 $u$ 的 marker 把线性表示写成 $AB$，reroot$(u)$ 通过一次 split 后拼成 $BA$；边的两个有向出现和循环相邻关系都没有改变。

设 $u,v$ 属于不同树。先分别 reroot$(u)$ 与 reroot$(v)$，使两条 tour 从对应端点开始。加入无向边 $\{u,v\}$ 后，新 tour 可按

的顺序 concatenate。两个新叶分别代表同一无向边的两个方向。link 前必须检查分量不同，否则结果不再是森林，Euler-tour-tree 的单 tour 不变量失效。

删除 $\{u,v\}$ 时，借助两个有向叶 $(u,v)$、$(v,u)$ 把循环 tour 在这两处切开，并删掉两个叶。余下两段各自闭合为一个 Euler tour，正对应删边后两个 represented components。只删除其中一个出现会留下无法配对的跨分量跳转，序列不再描述任何树。

切边为何正好得到两个分量 ​

树边 $\{u,v\}$ 是桥。一次 Euler walk 从 $u$ 经过 $(u,v)$ 进入 $v$ 侧子树，遍历完该侧所有边后，唯一能回到 $u$ 侧的有向出现正是 $(v,u)$。因此循环序列中这两个出现之间的一段完整覆盖 $v$ 侧，互补段覆盖 $u$ 侧。删掉二者并分别闭合，既不会漏边，也不会把两个分量交叉混合。

这条“桥的两次出现夹住一个分量”的不变量，是 cut 能用常数次 split/join 完成的原因；一般含圈图的边没有该性质，必须由外层动态图算法挑选生成森林。