OI-wiki 数据结构专题：Euler Tour Tree（欧拉游览树）——把动态树问题转化为序列区间操作的完整实现指南

OI-wiki 数据结构专题Euler Tour Tree欧拉游览树——把动态树问题转化为序列区间操作的完整实现指南【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikiEuler Tour Tree欧拉游览树简称 ETT是 OI-wiki 数据结构模块中用于解决动态树Dynamic Tree问题的一种核心数据结构。它的核心思想是把一棵树编码成一个特殊的 DFS 序列树的欧拉回路表示ETR从而把加边、删边、换根等动态树操作全部转化为序列的拆分Split与合并Merge操作再用平衡树等数据结构维护。读完本文你将掌握 ETT 的欧拉回路表示原理、MakeRoot / Insert / Delete 三大基本操作的序列变换细节、基于非旋 Treap 的完整 C 实现以及如何用 ETT 维护连通性、子树信息与受限的树链信息。本文以 docs/ds/ett.md 为主体并结合仓库中 docs/ds/code/ett/ 下的三份完整参考实现与 docs/ds/examples/ett/ 下的测试数据展开讲解。ETT 是什么把动态树问题化为序列问题动态树问题要求维护一棵不断变化的树森林支持加边、删边、换根等操作并在操作后高效回答连通性、子树信息、树链信息等查询。OI 中最常见的动态树工具是LCTLink-Cut Tree它擅长维护树链上的信息。而ETT 更适合维护子树信息——例如 ETT 可以维护子树最小值而 LCT 很难做到这一点。ETT 的基本思路如下将原树编码成一个与树一一对应的序列欧拉回路表示 ETR将动态树上的加边、删边、换根操作转化为常数次序列拆分与合并操作用任意支持序列区间操作的数据结构如 Splay、Treap 等平衡二叉搜索树维护该序列。只要底层数据结构支持所需的序列操作ETT 就能照常工作。若使用 Splay、非旋 Treap 这类平衡 BST每次序列操作的复杂度为 $O(\log n)$因此每个动态树操作也可以在 $O(\log n)$ 时间内完成若改用 B 树等多叉平衡搜索树理论上还能获得更优的常数甚至复杂度。需要强调的是ETT 本质上是一种思想——通过维护一个与原树一一对应的序列来维护原树。下面介绍的只是这种思想的一种可行实现与应用方式。树的欧拉回路表示ETR如果把一条树边看成两条有向边那么一棵树就可以表示成一个有向图的欧拉回路这称为树的欧拉回路表示Euler Tour RepresentationETR。OI-wiki 文档特别说明后面实际维护的序列是 ETR 的一个变种——把树中的每个点也看成自环加入 ETR由于原始论文作者没有另起新名仍沿用它为 ETR。构造算法给定一棵有根树 $T$可通过如下递归过程得到其欧拉回路表示$$ \begin{array}{ll} 1 \textbf{Input. } \text{A rooted tree }T\ 2 \textbf{Output. } \text{The dfs sequence of rooted tree }T\ 3 \operatorname{ET}(u)\ 4 \qquad \text{visit vertex }u\ 5 \qquad \text{for all child } v \text{ of } u\ 6 \qquad \qquad \text{visit directed edge } u \to v\ 7 \qquad \qquad \operatorname{ET}(v)\ 8 \qquad \qquad \text{visit directed edge } v \to u\ \end{array} $$即DFS 过程中每访问一次节点或一条有向边就把它追加到 $\operatorname{ETR}(T)$ 的尾部。设 $T$ 有 $n$ 个节点则树中有 $2n - 2$ 条有向边每个节点被访问一次、每条有向边被访问一次因此 $\operatorname{ETR}(T)$ 的长度为 $3n - 2$。把序列看作欧拉回路把每个点 $u$ 看成自环 $(u, u)$ 后$\operatorname{ETR}(T)$ 便是有向图中的一个欧拉回路。基于这一视角可以得到三种关键操作在欧拉回路的某处断开把它看成若干条边首尾相连的链把链在断开处重新粘合还原成欧拉回路通过新增一些边把两条链拼接成一条新的欧拉回路。这正是 ETT 各类动态树操作的基础换根 旋转回路加边 拼接回路删边 断开回路。ETT 的基本操作以下三个操作是 ETT 的基本操作每个都能转化为常数次序列操作因此其复杂度与序列操作同阶例如平衡树下的 $O(\log n)$。OI-wiki 文档同时强调下面的实现只是其中一种可行方案只要能用常数次序列操作拼出修改后的目标序列即可。MakeRoot(u)换根操作换根操作被转化为1 次序列拆分 1 次序列合并也可以理解为一次区间平移。设包含点 $u$ 的树为 $T$当前根为 $r$要将根换成 $u$。记 $T$ 对应的序列为 $L$将 $L$ 在自环 $(u, u)$ 处拆成 $L^1$ 与 $L^2$其中 $L^1$ 包含 $(u, u)$ 及其之前的所有元素$L^2$ 为剩余部分依次合并 $L^2$ 与 $L^1$ 即得到换根后的序列。直观理解欧拉回路是一个环对其做旋转不会改变环的结构也就不会改变树的结构只是把点 $u$ 旋转到了根的位置。Insert(u, v)加边操作加边操作被转化为2 次序列拆分 5 次序列合并。设 $u$ 所在的树为 $T_1$序列 $L_1$$v$ 所在的树为 $T_2$序列 $L_2$。先把 $L_1$ 在 $(u, u)$ 处拆成 $L_1^1, L_1^2$把 $L_2$ 在 $(v, v)$ 处拆成 $L_2^1, L_2^2$约定前半段包含自环。随后依次合并$$ L_1^2, \quad L_1^1, \quad [(u, v)], \quad L_2^2, \quad L_2^1, \quad [(v, u)] $$即可得到新树 $T$ 对应的序列 $L$。直观理解这相当于对两棵树各做一次换根操作然后在当前根的位置断开两个欧拉回路再用新加的两条有向边 $(u, v)$ 与 $(v, u)$ 把两个回路拼成一个新的欧拉回路。Delete(u, v)删边操作删边操作被转化为4 次序列拆分 1 次序列合并。设包含边 $(u, v)$ 与 $(v, u)$ 的树为 $T$对应序列为 $L$。将 $L$ 拆成$$ L_1, \quad [(u, v)], \quad L_2, \quad [(v, u)], \quad L_3 $$删边形成的两棵树的序列分别为 $L_2$ 与 $L_1, L_3$。需要注意序列 $L$ 中 $[(u, v)]$ 有可能出现在 $[(v, u)]$ 的后面此时先交换 $u$ 和 $v$ 再操作即可下文实现的Delete正是通过比较两条边在序列中的位置来决定是否交换。直观理解把欧拉回路从两条有向边处断开形成两条链再让两条链各自首尾相连形成两个新的欧拉回路。基于非旋 Treap 的实现OI-wiki 文档以**非旋 TreapFHQ Treap**为例给出完整实现要求读者事先了解用非旋 Treap 维护区间操作的内容可参考 docs/ds/treap.md。序列拆分Split与合并Merge是非旋 Treap 的基本操作此处不再赘述下面重点讲 ETT 特有的两个自底向上拆分原语。节点设计在仓库的实现ett_connectivity.cpp中每个序列元素是一个 Treap 节点Node字段包括from_/to_该元素对应的边有向边(from_, to_)自环(u, u)代表点 $u$left_/right_/parent_Treap 的左右儿子与父指针父指针是实现自底向上拆分的关键priority_随机优先级由std::mt19937生成size_子树大小由Maintain()在旋转/合并时维护。此外DynamicForest维护了两张映射表vertices_[i]记录点 $i$ 对应的自环节点tree_edges_[u][v]记录有向边 $(u, v)$ 对应的节点供加边/删边时 $O(\log n)$ 定位。关键原语GetPosition 与 SplitUp2 / SplitUp3普通非旋 Treap 的Split是按排名序列位置切分但 ETT 的加边/删边拿到的是节点指针因此需要先求出该节点在序列中的位置再调用Split或者直接自底向上完成拆分省去一次定位的开销。GetPosition(p)利用parent_指针从节点 $p$ 出发向上累加左子树大小即可在 $O(\log n)$ 内求出 $p$ 在序列中的从 1 开始的下标实现见 ett_connectivity.cpp。SplitUp2(u)把 $u$ 所在序列在 $u$ 处拆成两份第一份包含 $u$ 及其之前的所有元素第二份包含 $u$ 之后的元素。OI-wiki 文档给出的是自底向上的实现从 $u$ 对应节点向根跳跃的过程中利用二叉搜索树的性质判断每个节点在 $L$ 中位于 $u$ 之前还是之后从而确定它属于拆分后的哪一棵树。这种实现比先求位置再Split更高效因为它只做一次 $O(\log n)$ 的向上遍历。/* * Bottom up split treap p into 2 treaps a and b. * - a: a treap containing nodes with position less than or equal to p. * - b: a treap containing nodes with postion greater than p. * * In the other word, split sequence containning p into two sequences, the first * one contains elements before p and element p, the second one contains * elements after p. */ static std::pairNode*, Node* SplitUp2(Node* p) { Node *a nullptr, *b nullptr; b p-right_; if (b) b-parent_ nullptr; p-right_ nullptr; bool is_p_left_child_of_parent false; bool is_from_left_child false; while (p) { Node* parent p-parent_; if (parent) { is_p_left_child_of_parent (parent-left_ p); if (is_p_left_child_of_parent) { parent-left_ nullptr; } else { parent-right_ nullptr; } p-parent_ nullptr; } if (!is_from_left_child) { a Merge(p, a); } else { b Merge(b, p); } is_from_left_child is_p_left_child_of_parent; p-Maintain(); p parent; } return {a, b}; }SplitUp3(u)在SplitUp2基础上稍作修改即可把序列在 $u$ 处拆成三份$u$ 之前的元素、$u$ 本身、$u$ 之后的元素实现见 ett_subtree_size.cpp返回{a, c, b}三元组。MakeRoot(u)基于SplitUp2与Merge即可实现见 ett.md 与 ett_subtree_size.cppvoid MakeRoot(int u) { Node* vertex_u vertices_[u]; auto [L1, L2] Treap::SplitUp2(vertex_u); Treap::Merge(L2, L1); }Insert(u, v)基于SplitUp2与Merge即可实现见 ett_connectivity.cpp与上文2 次拆分 5 次合并一一对应void Insert(int u, int v) { Node* vertex_u vertices_[u]; Node* vertex_v vertices_[v]; Node* edge_uv AllocateNode(u, v); Node* edge_vu AllocateNode(v, u); tree_edges_[u][v] edge_uv; tree_edges_[v][u] edge_vu; auto [L11, L12] Treap::SplitUp2(vertex_u); auto [L21, L22] Treap::SplitUp2(vertex_v); Node* L L12; L Treap::Merge(L, L11); L Treap::Merge(L, edge_uv); L Treap::Merge(L, L22); L Treap::Merge(L, L21); L Treap::Merge(L, edge_vu); }注意合并顺序先把 $(u, u)$ 之前的半段$L_{11}$挪到 $u$ 自环之后再把新边 $(u, v)$、$v$ 自环所在半段$L_{22}$、$L_{21}$、最后补上反向边 $(v, u)$使得序列恰好是合法欧拉回路。仓库实现中还通过assert(GetSize(L11) position_u)校验拆分位置与GetPosition的结果一致。Delete(u, v)基于SplitUp3与Merge即可实现见 ett_connectivity.cpp。首先用GetPosition比较两条有向边 $(u,v)$ 与 $(v,u)$ 在序列中的先后若 $(u,v)$ 在 $(v,u)$ 之后则交换二者保证按先出现的边切分随后两次SplitUp3得到五段合并 $L_1$ 与 $L_3$ 即完成删边void Delete(int u, int v) { Node* edge_uv tree_edges_[u][v]; Node* edge_vu tree_edges_[v][u]; tree_edges_[u].erase(v); tree_edges_[v].erase(u); int position_uv Treap::GetPosition(edge_uv); int position_vu Treap::GetPosition(edge_vu); if (position_uv position_vu) { std::swap(edge_uv, edge_vu); std::swap(position_uv, position_vu); } auto [L1, uv, _] Treap::SplitUp3(edge_uv); auto [L2, vu, L3] Treap::SplitUp3(edge_vu); Treap::Merge(L1, L3); FreeNode(edge_uv); FreeNode(edge_vu); }维护连通性点 $u$ 与点 $v$ 连通当且仅当它们属于同一棵树即自环 $(u, u)$ 与 $(v, v)$ 属于同一个 $\operatorname{ETR}(T)$。在 Treap 实现中只需判断两个节点所在Treap 的根是否相同——仓库用FindRoot沿parent_指针向上找到根并比较见 ett_connectivity.cpp 与IsConnected。例题P2147「SDOI2008」洞穴勘测这是维护连通性的模板题支持三种操作Connect u v在 $u, v$ 之间加边对应InsertDestroy u v删除边 $(u, v)$对应Delete注意输入可能交换端点Query u v询问 $u, v$ 是否连通对应IsConnected。参考实现见 docs/ds/code/ett/ett_connectivity.cpp。仓库自带的测试数据 ett_connectivity.in 与 ett_connectivity.ans 展示了典型的操作序列与期望输出200 5 Query 123 127 Connect 123 127 Query 123 127 Destroy 127 123 Query 123 127No Yes No可以看到未连边时Query返回NoConnect后返回YesDestroy 127 123端点顺序与加边相反后再次Query返回No验证了Delete中交换 $u,v$分支的正确性。维护子树信息这是 ETT 相对 LCT 的核心优势。以维护子树节点数量为例对于 $\operatorname{ETR}(T)$ 中的每个元素若它对应树中的点即自环令其权值为 $1$若它对应树中的边令其权值为 $0$。此时整棵树的节点数量就等于序列元素权值和而序列权值和正是非旋 Treap 的经典操作在每个节点额外维护num_vertex_即可见 ett_subtree_size.cpp 中Maintain()对num_vertex_的累加。类似地子树最小值等操作也可以转化为序列区间最小值等平衡树经典操作来维护。例题LOJ #2230「BJOI2014」大融合题目要求森林上不断加边并询问经过某条边后删去该边所得两棵子树大小的乘积。参考实现见 docs/ds/code/ett/ett_subtree_size.cpp其核心技巧是查询时先Delete(u, v)拆出两棵树分别用GetComponentNumberOfVertex求两侧的点数相乘得到答案再把边Insert(u, v)回去。仓库测试数据 ett_subtree_size.in 与 ett_subtree_size.ans 给出了可复现的验证场景8 6 A 2 3 A 3 4 A 3 8 A 8 7 A 6 5 Q 3 86此时树为2-3-4、3-8-7与孤点5、6删去边 $(3,8)$ 后含 3 的一侧有 3 个点含 8 的一侧有 2 个点乘积为 $3 \times 2 6$与答案一致。维护树链信息ETT 也可以维护一部分树链信息常用技巧是借助括号序的性质把树链信息转化成区间信息再借助序列数据结构维护。但该技巧有一个硬性前提所维护的信息必须满足可减性例如点权和、点权异或和等。OI-wiki 文档同时指出了两个重要局限前面介绍的动态树操作对应的序列操作可能把括号序中的右括号移动到左括号之前从而破坏括号匹配结构。因此维护树链点权等信息时需要额外小心操作过程中不能改变对应左右括号的先后顺序这往往要求重新思考动态树操作对应的序列操作甚至重新设计所维护的 DFS 序ETT 很难维护树链修改如对一条路径整体加值。例题「星际探索」BZOJ 3786本题的动态树操作只有换父亲把某个节点的父亲改为另一个节点可以看成删边 加边但直接这样做可能改变括号先后顺序。解决方案是把点权转化为边权维护树的括号序换父亲操作转化为把整个子树对应的括号序列平移到新父亲左括号的后面。参考实现见 docs/ds/code/ett/ett_1.cpp。该实现额外支持对子树区间加值add利用tag懒标记与pd/pds记录括号符号以实现正负号正确的区间加与子树求和query。仓库测试数据 ett_1.in 与 ett_1.ans 展示了Q查询、F子树加、C换父亲三种操作的组合3 1 1 4 5 7 5 Q 2 F 1 3 Q 2 C 2 3 Q 29 15 25初始树为1的两个儿子2、3权值分别为 4、5、7。Q 2返回点 2 位置之前的序列前缀和 9即 $45$F 1 3给全树加 3 后Q 2得 15C 2 3把 2 变成 3 的儿子后括号序变为s1, s3, s2, e2, e3, e1Q 2返回 25$7108$。三组输出与手算结果完全一致。参考资料本文内容基于 OI-wiki 仓库 docs/ds/ett.md实现细节与测试数据来源于 docs/ds/code/ett/ 与 docs/ds/examples/ett/。相关概念可进一步参阅仓库中 docs/ds/treap.md非旋 Treap 区间操作、docs/ds/lct.mdLCT 及其与 ETT 的对比等章节。ETT 的原始理论出处为Robert E. Tarjan.Dynamic trees as search trees via euler tours, applied to the network simplex algorithmHenzinger et al.Randomized fully dynamic graph algorithms with polylogarithmic time per operation。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考