企业官网建设流程全解析

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

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

Euler 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 中最常见的动态树工具是LCT（Link-Cut Tree），它擅长维护树链上的信息。而ETT 更适合维护子树信息——例如 ETT 可以维护子树最小值，而 LCT 很难做到这一点。

ETT 的基本思路如下：

1. 将原树编码成一个与树一一对应的序列（欧拉回路表示 ETR）；
2. 将动态树上的加边、删边、换根操作转化为常数次序列拆分与合并操作；
3. 用任意支持序列区间操作的数据结构（如 Splay、Treap 等平衡二叉搜索树）维护该序列。

只要底层数据结构支持所需的序列操作，ETT 就能照常工作。若使用 Splay、非旋 Treap 这类平衡 BST，每次序列操作的复杂度为 $O(\log n)$，因此每个动态树操作也可以在 $O(\log n)$ 时间内完成；若改用 B 树等多叉平衡搜索树，理论上还能获得更优的常数甚至复杂度。

需要强调的是，ETT 本质上是一种思想——通过维护一个与原树一一对应的序列来维护原树。下面介绍的只是这种思想的一种可行实现与应用方式。

树的欧拉回路表示（ETR）

如果把一条树边看成两条有向边，那么一棵树就可以表示成一个有向图的欧拉回路，这称为树的欧拉回路表示（Euler Tour Representation，ETR）。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 文档以**非旋 Treap（FHQ 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::pair<Node*, 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.cpp）：

void 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$ 之间加边（对应Insert）；
• Destroy 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 127

No Yes No

可以看到：未连边时Query返回No；Connect后返回Yes；Destroy 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 8

6

此时树为2-3-4、3-8-7与孤点5、6；删去边 $(3,8)$ 后，含 3 的一侧有 3 个点，含 8 的一侧有 2 个点，乘积为 $3 \times 2 = 6$，与答案一致。

维护树链信息

ETT 也可以维护一部分树链信息，常用技巧是借助括号序的性质把树链信息转化成区间信息，再借助序列数据结构维护。但该技巧有一个硬性前提：所维护的信息必须满足可减性（例如点权和、点权异或和等）。

OI-wiki 文档同时指出了两个重要局限：

1. 前面介绍的动态树操作对应的序列操作，可能把括号序中的右括号移动到左括号之前，从而破坏括号匹配结构。因此维护树链点权等信息时需要额外小心：操作过程中不能改变对应左右括号的先后顺序，这往往要求重新思考动态树操作对应的序列操作，甚至重新设计所维护的 DFS 序；
2. 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 2

9 15 25

初始树为1的两个儿子2、3，权值分别为 4、5、7。Q 2返回点 2 位置之前的序列前缀和 9（即 $4+5$）；F 1 3给全树加 3 后Q 2得 15；C 2 3把 2 变成 3 的儿子后，括号序变为s1, s3, s2, e2, e3, e1，Q 2返回 25（$7+10+8$）。三组输出与手算结果完全一致。

参考资料

本文内容基于 OI-wiki 仓库 docs/ds/ett.md，实现细节与测试数据来源于 docs/ds/code/ett/ 与 docs/ds/examples/ett/。相关概念可进一步参阅仓库中 docs/ds/treap.md（非旋 Treap 区间操作）、docs/ds/lct.md（LCT 及其与 ETT 的对比）等章节。

ETT 的原始理论出处为：

• Robert E. Tarjan.Dynamic trees as search trees via euler tours, applied to the network simplex algorithm；
• Henzinger 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