ETT学习笔记

Querainy · 2020-02-28 13:47:02 · 个人记录

ETT(Euler Tour Tree)是一种动态树数据结构。它可以简单地维护子树可合并信息，但是不能简单地维护树链信息。

树的Euler Tour(欧拉回路)是把树上的边变成两条有向边得到的欧拉回路。其实我觉得这个东西和欧拉序没有什么区别......所以这里所说的都是"欧拉序"。

ETT的思想是考虑动态树操作对欧拉序的影响，然后用平衡树维护。

1. \operatorname{Link}(u,v)

抽象地推导一下。先看图。

这里\text{A,B}是从\text{root}走到u或v并走过了任意棵u或v的子树的欧拉序，\text{C,D}是从u或v走到\text{root}的欧拉序。显然u所在树的欧拉序是\text{A }u\text{ B}，v所在的树是\text{C }v\text{ D}。

接下来考虑如何构造\operatorname{Link}后的合法欧拉序。我们让u所在树的根r成为新的根。从r开始先按\text{A}的顺序走到u，然后沿(u,v)走到v，然后按\text{D C}走完v所在的整棵树，然后沿(v,u)走回去，最后按\text{B}走回r。

简单地说，我们任意找一个u和一个v，然后按它们把两个欧拉序断开，以u所在树为例，把原欧拉序断开形成前半段以u结尾的\text{A}和后半段\text{B}。然后按\text{A }v\text{ D C }u\text{ B}的顺序接起来。注意\text{D}的结尾和\text{C}的开头都是v所在树的根，所以要去掉一个，这里我们约定去掉后面的。

然后举个具体的例子 :

2. \operatorname{Cut}(u,v)

我们把\operatorname{Link}的过程反过来，先找到uv和vu，然后把它们断开，按照\operatorname{Link}的拼接顺序分别找到\text{A D C B}，然后拼成\text{A B}和\text{C D}两段。记得把后面被去掉的根加回来。

找uv可以每个点维护一个map，u.map[v]表示后面是v的u的位置。

3. \operatorname{Reroot}(u)

设原来的根为r。考虑从任意一个u开始到欧拉序的最后的一段是从u到r的一段，而在这个u前面的是从r到u的一段，且由于两段构成完整的欧拉序，两段是边不重合的。

所以把从任意一个u开始(包括u)到欧拉序的最后的一段拿出来放到前面去。

因为原来的欧拉序开头结尾都是r，所以要在原来的欧拉序最后或最前删掉一个r。而且因为"从r到u的一段"不包括u，所以还要在合并后的欧拉序最后加上一个u。

4. 通过\operatorname{Reroot}简单实现\operatorname{Link}和\operatorname{Cut}