图解ETT（Euler Tour Tree）
ヾ(≧∇≦*)ゝ 联合省选 2025 RP++,RK--;
起因：某次 %你赛中出现了这样一个题：
给定一棵带点权的树。我们对这棵树进行若干次删点操作，直到删除所有点为止。第
i 次删点操作（i 从1 开始标号）如下：
- 如果
i 是奇数，那么删除每个连通块内点权最小的点；- 如果
i 是偶数，那么删除每个连通块内点权最大的点。问多少次操作后树上所有点被删完了。
dalao 们都有智慧的做法，但是对我来说，智慧不够就只能使用数据结构来凑了。。(๑˃ᴗ˂)ﻭ
对于暴力的做法来说，瓶颈是每次删完点之后统计每个联通块之内的
花费 2h 码了将近 400 lines，8k+ 的代码，其中 ETT 就有 250+ lines。(´∀｀)♡
然后 0.5h 进行 debug，最后一分钟测完样例提交。
最后喜提最劣解，拼尽全力卡进时限，变成了
ETT 有什么用？
你说得对，但是 ETT 是一种可以解决动态树问题的数据结构，你将扮演一位名为 "OIer" 的神秘角色，在数百行代码中维护加边与删边，同时逐步发掘“子树信息”的真相。
LCT vs. ETT vs. SATT
LCT是最常见的一种动态树，基于实链剖分，即将原树分成实链和虚链，使用若干棵 Splay （即辅助树）来维护实链，不同的辅助树之间通过虚边连接。可以使用 access 和 makeroot 操作来灵活的切换实链和虚链。它的结构特点意味着它可以方便的维护树链信息，但是对于子树信息的维护并不方便。
ETT通过维护一种和原树一一对应的序列——欧拉环游序表示（Euler Tour Representation），并且将原树通过序列映射到数据结构（如 FHQ Treap，Splay 等）上面来维护原树的信息。它的结构特点意味着它可以方便的维护子树信息，如上面的题目中提到的子树
SATT是基于树收缩理论的一种动态树，使用 Splay 维护 Rake 节点和 Compress 节点代表树收缩过程中的 Rake 和 Compress 操作。它不仅可以维护树链信息，也可以维护子树信息，但是我不会。据爆切了 P5649 Sone1 的 lkrkerry dalao 说，学习 SATT 的难度约等于学完 LCT 再学一遍 LCT （尊嘟假嘟）。
什么是欧拉环游序
这是一棵平平无奇的树：
现在把它的每一条无向边换成两条相反的有向边：
这样树就变成了一个欧拉图，遍历就可以得到它的欧拉环游序。
但是这样并不便于维护，所以我们将树上的每一个点变成一个自环：
此时它依然是一个欧拉图，我们就可以使用数据结构维护它上面每一条边（包括自环）得到欧拉环游树了。
ETT的基本操作
换根
假如我现在有一棵以 1 号节点为根的 ETT ，其形态如下：
其中绿色的边是使用数据结构维护的欧拉环游序，可以看到它的链在根节点处是断开的。
如果我们要对一个 ETT 进行换根操作，就是要把这个断点的位置给转移到其他节点上面，因为欧拉回路是一个环，所以也可以等效于旋转这个欧拉环游序。
假设我们要将树根切换到 10 号节点：
- 先将原来的链从 10 号节点处切开成蓝色的 L1 和红色的 L2：
-
然后再将 L2 和 L1 连接起来：
这样树的根就这么水灵灵的被切换到 10 号点了。
加边
考虑以下的两棵树，形成两个欧拉回路，各自有各自的根节点。
如果我们想要给它们加边使得它们处于同一个联通块之内，就要把两个欧拉回路合并成一个欧拉回路。
如果我们想要连接的是 8 和 13 两个节点:
- 将红色的树链从 8 号点断开，成为红色的
L(1,1) 和紫色的L(1,2) 两条链；同时将蓝色的树链从 13 号点断开，成为蓝色的L(2,1) 和绿色的L(2,2) 两条链。
（为了画图方便，接下来把右边的树旋转 180 度）
- 在平衡树上建立两个新的节点，代表原树上新增的边，一条是
8\to 13 （记为E_1 ），另外一条13\to8 （记为E_2 ）。 - 可以使用
std::map维护每个节点连接的边。
- 将
L(1,2),L(1,1),E_1,L(2,2),L(2,1),E_2 顺次连接起来：
这样就成功的在
删边
删边的操作就是把原来欧拉回路的环断开，删除代表
假设我们要删除
- 先将树链在边
8\to13 处和边13\to8 处分开，成为L_1,L_2,L_3 三条树链和E_1,E_2 两条边。
- 删除
E_1,E_2 两条单独的边。
- 这时发现左边的树的树链是不完整的，所以将
L_3,L_1 连接起来。
最后得到两棵树。
实现方式
通过对上面操作的观察，可以发现操作很多都与序列的连接和分裂有关，容易想到可以使用无旋 Treap 来处理这些操作。
无旋 Treap 比较基本的 Split,Merge 这些操作都容易实现，按照普通平衡树来写即可。
ETT 使用的无旋 Treap 还有以下特有的操作：
Split2
顾名思义，这个操作就是把一个树分裂成两颗。与普通的 Split 不同的是，普通的 Split 需要给出树的根节点，将树按照给定的方式（比如按照大小或者键值）来分成两个，而 Split2 是给定树上任意的节点，将序列中在该节点之前（包含当前节点）和在该节点之后的两个部分分开。
要实现这一点，需要在树上的每个节点中记录其父亲。在从当前节点往上跳的过程中，判断其在原序列中相对于给定节点的位置，并且合并到左右两个树上。
Split3
顾名思义，这个操作就是把树分裂成三份，也就是在原序列中在给定节点之前，之后的部分以及给定节点本身。
实现上与 Split2 只是略有改动。
其他操作
比如加边，删边等操作都可以通过树链的分裂，合并等来完成。
后记
感觉理解起来，比 LCT 要简单吧。
P4219 [BJOI2014] 大融合 附赠一道练手水题
namespace ett {
struct node {
int sz, wt, val;
pair<int, int> mx, mi;
node *ls,*rs,*die;
int from, to, isv;
inline void init(int x, int y, int z) {
sz = 1, wt = rd();
from = x, to = y, val = z;
ls = nullptr, rs = nullptr, die = nullptr;
if ((isv = (from == to))) { //this node is a vertex
mx = mi = {z, x};
} else { //this node is an edge
mx = {-0x3f3f3f3f, 0};
mi = {0x3f3f3f3f, 0};
}
}
inline node(int x, int y, int z) {
sz = 1, wt = rd();
from = x, to = y, val = z;
ls = nullptr, rs = nullptr, die = nullptr;
if ((isv = (from == to))) { //this node is a vertex
mx = mi = {z, x};
} else { //this node is an edge
mx = {-0x3f3f3f3f, 0};
mi = {0x3f3f3f3f, 0};
}
}
inline void pushup() {
sz = 1;
if (isv) {
mx = mi = {val, from};
} else {
mx = {-0x3f3f3f3f, 0};
mi = {0x3f3f3f3f, 0};
}
if (ls) {
sz += ls->sz;
ls->die = this;
mx = max(mx, ls->mx);
mi = min(mi, ls->mi);
}
if (rs) {
sz += rs->sz;
rs->die = this;
mx = max(mx, rs->mx);
mi = min(mi, rs->mi);
}
}
};
int n;
vector<node*> v;
vector<map<int, node*> > e;
int cnt;
inline int getsz(node* p) {
return p == nullptr ? 0 : p->sz;
}
inline node* findrt(node* p) {
if (!p)return nullptr;
while (p->die != nullptr)p = p->die;
return p;
}
inline node* newnode(int x, int y, int z) {
node* p = new node(x, y, z);
return p;
}
inline void delnode(node* p) {
if (p) {
delete p;
p = nullptr;
}
}
inline node* merge(node* a, node* b) {
if (a == nullptr)return b;
if (b == nullptr)return a;
if (a->wt < b->wt) {
a->rs = merge(a->rs, b);
a->pushup();
return a;
} else {
b->ls = merge(a, b->ls);
b->pushup();
return b;
}
}
inline int getp(node* p) {
int pos = getsz(p->ls) +1;
while (p) {
if (p->die && p == p->die->rs) {
pos += getsz(p->die->ls) +1;
}
p = p->die;
}
return pos;
}
inline pair<node*, node*> split(node* p, int k) {
if (!p)return {nullptr, nullptr};
pair<node *, node * > res;
if (getsz(p->ls) < k) {
auto rres = split(p->rs, k - getsz(p->ls) -1);
p->rs = rres.first;
res.first = p, res.second = rres.second;
} else {
auto lres = split(p->ls, k);
p->ls = lres.second;
res.first = lres.first, res.second = p;
}
p->pushup();
if (res.first)res.first->die = nullptr;
if (res.second)res.second->die = nullptr;
return res;
}
inline pair<node*, node*> split2(node* p) {
node *a = nullptr,*b = nullptr;
b = p->rs;
if (b)b->die = nullptr;
p->rs = nullptr;
bool f1 = 0, f2 = 0;
while (p) {
node* die = p->die;
if (die) {
f1 = (die->ls == p);
if (f1) {
die->ls = nullptr;
} else {
die->rs = nullptr;
}
p->die = nullptr;
}
if (!f2) {
a = merge(p, a);
} else {
b = merge(b, p);
}
f2 = f1;
p->pushup();
p = die;
}
return {a, b};
}
inline tuple<node*, node*, node*> split3(node* p) {
node* a = p->ls;
if (a)a->die = nullptr;
p->ls = nullptr;
node* b = p->rs;
if (b)b->die = nullptr;
p->rs = nullptr;
node* c = p;
bool f1 = 0, f2 = 0;
node* die = p->die;
if (die) {
f1 = (die->ls == p);
if (f1) {
die->ls = nullptr;
} else {
die->rs = nullptr;
}
p->die = nullptr;
}
f2 = f1;
p->pushup();
p = die;
while (p) {
node* die = p->die;
if (die) {
f1 = (die->ls == p);
if (f1) {
die->ls = nullptr;
} else {
die->rs = nullptr;
}
p->die = nullptr;
}
if (!f2) {
a = merge(p, a);
} else {
b = merge(b, p);
}
f2 = f1;
p->pushup();
p = die;
}
return {a, c, b};
}
inline void init(int x) {
n = x;
v.resize(x + 5);
e.resize(x + 5);
for (int i = 1; i <= n; i++) {
v[i] = newnode(i, i, w[i]);
}
}
inline void makert(int x) {
node* p = v[x];
int pos = getp(p);
auto p1 = split2(p);
auto l1 = p1.first, l2 = p1.second;
merge(l2, l1);
}
inline void link(int x, int y) {
node *vu = v[x],*vv = v[y];
node* euv = newnode(x, y, 0);
node* evu = newnode(y, x, 0);
e[x][y] = euv, e[y][x] = evu;
auto p1 = split2(vu);
auto p2 = split2(vv);
auto l11 = p1.first, l12 = p1.second;
auto l21 = p2.first, l22 = p2.second;
node* res = nullptr;
res = merge(res, l12);
res = merge(res, l11);
res = merge(res, euv);
res = merge(res, l22);
res = merge(res, l21);
res = merge(res, evu);
}
inline void cut(int x, int y) {
node *euv = e[x][y],*evu = e[y][x];
e[x].erase(y), e[y].erase(x);
int puv = getp(euv), pvu = getp(evu);
if (puv > pvu) {
swap(euv, evu);
swap(puv, pvu);
}
auto p1 = split3(euv);
auto l1 = get<0>(p1), uv = get<1>(p1);
auto p2 = split3(evu);
auto l2 = get<0>(p2), vu = get<1>(p2), l3 = get<2>(p2);
l1 = merge(l1, l3);
delnode(euv), delnode(evu);
}
inline pair<int, int> qmx(int x) {
node* p = v[x];
node* rt = findrt(p);
return rt ? rt->mx : make_pair(0, 0);
}
inline pair<int, int> qmi(int x) {
node* p = v[x];
node* rt = findrt(p);
return rt ? rt->mi : make_pair(0, 0);
}
inline void release() {
for (int i = 1; i <= n; i++) {
for (auto j : e[i])delnode(j.second);
}
for (int i = 1; i <= n; i++)delnode(v[i]);
}
}