Euler Tour Tree 学习

· · 个人记录

本文不知道有没有错，因为作者没写过代码太离谱了。。当然现在有 Top Tree 这个也不是特别有用了，在 Werneck 的论文中提到， ETT 是最简单的动态树结构，也没有对 ETT 的操作进行详细的讲解，因为这些操作实在是太过于简单了。。

基本操作

一般来说我们大概实现下面几种操作

一些概念

首先，对于一棵自由树

我们将其 Euler Tour 写出来是

[A]-AB-[B]-BA-[A]-AC-[C]-CE-[E]-EC-[C]-CF-[F]-FC-[C]-CA-[A]-AD-[D]-DE-[E]-ED-[D]-DA

这正是

每条边经过两次，而对于每个节点 x 来说经过 \deg(x) 次，这里是对于有根树的 Euler Tour 而我们所处理的往往是自由树，没有固定的根。

此时 Tarjan 提出我们对于一个节点的访问只保留一次，而且我们并不在意保留哪一次，然后 Euler Tour 就变成了一个循环双链表的表示。

[A]-AB-[B]-BA-AC-[C]-CE-[E]-EC-CF-[F]-FC-CA-AD-[D]-DG-[G]-GD-DA

然后我们将头尾也连起来即可。 Werneck 提出在任意点断开这个循环双链表，并存储在二叉搜索树中，使得该二叉搜索树的中序遍历为这个序列即可（既然是循环链表，当然不用在乎从哪里断开）。

我们在这里加入更强的限制，即让中序遍历第一个为该树的根，换句话说，我们只维护有根树，但是支持 \operatorname{evert}(x) 操作。

接下来我们观察上述基本操作对于该序列的影响。

\operatorname{findroot}(x)

寻找序列的第一个元素，对应到二叉搜索树中即 left most 的节点。

\operatorname{evert}(x)

为了支持 \operatorname{evert}(x) 操作，我们需要有一个映射能快速找到 x 在 ETT 中的指针，然后将 x 前的所有序列按顺序放到最后即可。在 Splay 树中这将需要均摊 O(\log n) 的时间。

\operatorname{cut}(x)

为了支持这个操作，我们需要能够比较快速的查询 \operatorname{parent}(x) ，但是直接使用 ETT 的方法我不会，于是借助 LCT 来完成。那么我们先 \operatorname{evert}(\operatorname{parent}(x)) 然后此时序列大概是

[parent(x)]-...-(parent(x),x)-...-(x,parent(x))-...

我们使边 (\operatorname{parent}(x),x) 在 Splay 树中对应的节点成为二叉搜索树的根，然后 (x,\operatorname{parent}(x)) 成为其右子树，此时

我们一定要保证 \operatorname{parent}(x) 在 A 中且 x 在 B 中，这样我们就完成了 \operatorname{cut}(x) 操作。而因为 \operatorname{parent}(x) 是中序遍历第一个，必然在 A 中且只能通过边 (\operatorname{parent}(x),x) 到达 x 所以 x 只能在 B 中，我们无需额外的操作。

\operatorname{cut}(x,y)

与上面类似的做法即可，如果保证边 (x,y) 存在，那么可以省略验证 \operatorname{parent}(x) 的步骤。

\operatorname{link}(x,y)

我们只需验证 x 和 y 所在的树是否为同一棵，若不是则将先 \operatorname{evert}(x) 再 \operatorname{evert}(y) 。后按照上述 \operatorname{cut}(x,y) 的方法创建这两个边的节点即可。

\operatorname{findmin}(x)

通过 LCT 找到 \operatorname{parent}(x) 后仿照上述 \operatorname{cut}(x) 的操作即可。

子树加/子树和

因为没有链的询问，所以我们只需额外记录一个 size[x] 表示以 x 为根的子树大小 size[x] = size[left_child(x)] + size[right_child(x)] + int(is_vertex(x)); 这样应用类似于线段树 lazy propagation 即可。