Euler Tour Tree

表示不变量 ​

对 represented forest 中每棵无向树 $T$，把每条边 $\{u,v\}$ 变成两个有向出现 $(u,v)$ 与 $(v,u)$。从任意根开始沿每条有向边恰走一次，得到长度 $2|E(T)|$ 的循环 Euler tour。为使孤立顶点也有序列位置，并方便顶点值聚合，常再给每个顶点放一个自出现 marker。

每棵树的循环 tour 从任意位置切开，存入支持以下序列操作的平衡搜索树：

$$\mathrm{split},\mathrm{concatenate},\mathrm{aggregate}.$$

叶按 tour 顺序排列，内部节点维护大小和幺半群摘要。结构树只是序列容器；它的父子关系不是 represented tree 的父子关系。每个 represented 顶点或有向边保存指向其叶出现的句柄，以便在 $O(\log n)$ 时间定位并切分。

选定实现下的复杂度 ​

若序列使用隐式随机 Treap，则对任意预先固定的合法操作序列，split/join 的期望时间为 $O(\log n)$；若使用具有 join/split 保证的确定性平衡树，可得到相应最坏 $O(\log n)$。以下以 Treap 版本为例：

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

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

reroot、link 与 cut ​

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

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

$$T_u(u,v)T_v(v,u)$$

的顺序 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 完成的原因；一般含圈图的边没有该性质，必须由外层动态图算法挑选生成森林。

具体例子：切开一条树边 ​

考虑树边

$$\{a,b\},\{b,c\},\{b,d\}.$$

某个循环表示可含片段

$$(a,b),(b,c),(c,b),(b,d),(d,b),(b,a).$$

删除 $\{b,c\}$ 时，去掉 $(b,c)$ 与 $(c,b)$；夹在两者之间的 tour 只含顶点 $c$ 的 marker，形成一个分量，余下出现仍组成 $a-b-d$ 的 tour。若后来 link$(c,d)$，旋转两条序列后插入 $(c,d),(d,c)$ 即可重新合并。

聚合中的重复计数 ​

顶点会在 Euler walk 中多次出现。若每个出现都存同一顶点权值，分量和会按度数重复计数。常见修复是只让每个顶点的专用 marker 贡献权值，所有有向边出现贡献单位元；这样序列根摘要恰为分量顶点聚合。边聚合则可只让一对有向出现中的指定代表贡献，或按需求设计可抵消编码。

静态 DFS preorder 中子树是一个连续区间；动态无向 Euler tour 的主要语义却是整棵分量的循环表示。若固定根并精心安排 entry/exit marker，可扩展某些子树查询，但 reroot、link 与 cut 会改变区间语义，必须单独证明。

失败边界与 Link–Cut 对照 ​

ETT 能直接判断分量、维护分量摘要，并作为 全动态连通性公理库全动态连通性Fully dynamic connectivity · Dynamic graph connectivity以分层生成森林和 replacement-edge 搜索维护在线边插入删除下的无向图连通性，并用边层级单调提升证明多对数摊还更新界。的生成森林容器。任意两点简单路径在循环 tour 中通常不是一个连续片段，所以路径最大值或路径乘积不如 Link–Cut Tree公理库Link–Cut TreeLink-cut tree · 动态树以 preferred-path 分解和辅助伸展树维护动态森林，在对数摊还时间内支持换根、连边、断边与路径聚合。直接。

结构只维护森林。若外层图含非树边，ETT 可以保存选定生成森林，却不会自动寻找删树边后的 replacement edge；这正是全动态连通性算法需要额外层级和边集合的原因。

参考资料

• Monika R. Henzinger and Valerie King, “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation,” Journal of the ACM 46(4), 1999.
• David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig, “Sparsification — A Technique for Speeding Up Dynamic Graph Algorithms,” JACM 44(5), 1997.
• Erik D. Demaine, Advanced Data Structures, MIT 6.851 lecture notes, Euler-tour trees and dynamic forests.