jerry3128 大佬的 题解 和 浅谈ETT 都讲得很好，我这里补充一下换根和删边的细节，以及提供一个 splay 的 ETT 实现。
¶ 换根
括号序的 ETT 支持链查询，但是不支持换根。欧拉序的ETT支持换根，但是（应该）不支持链查询。
假设要将根从 a 换成 u。先找到 u 的任意一次出现的位置，这样原欧拉序一定为 aAuBa 的形式。由于其中 u 不一定是其第一次出现，所以 A 中也可以有 u，但是这不影响。我们观察一下，原先的欧拉序是先从 a 沿着 A 走到 u，再沿着 B 走回去。那么把根换成 u 后，只需要从 u 出发，沿着 B 走到 a，再沿着 A 走回 B 即可，生成的欧拉序为 uBaAu。所以换根的算法就是先把欧拉序拆成 aA 和 uBa 两部分，然后把第一个 a 删掉，再将 A 接到 uBa 后，成为 uBaA，最后再将 u 接到后面，变成 uBaAu。
¶ 删边
假如要删掉 u 和 v 之间的边。我们不知道 u 和 v 谁是父节点，所以考虑先将 u 换为根，这样 u 一定是 v 的父节点。那么欧拉序就是 AuvBvuC。显然，uv 和 vu 之间就是遍历 v 所在的子树的欧拉序。我们只需要把 vBv 拿出来，得到 Au vBv uC 三个序列，然后把 uC 里的 u 删掉，再将 Au 和 C 连接起来，就得到两个欧拉序列 AuC 和 vBv，这就是删掉 u 和 v 之间的边之后得到的两棵树的欧拉序。由于 uv 和 vu 在欧拉序中都出现且仅出现一次，所以可以用哈希表来保存每个形如 uv 的序列的 v 在欧拉序里的位置（一般是记录节点编号），这样就能快速找到切分点了。这个哈希表只在切分和连接欧拉序列的时候才需要更新。
此外，由于哈希表的最坏时间复杂度很糟糕，所以如果怕被卡，可以用 map
存，反正一个操作的总时间复杂度也是
¶ 吐槽
很多资料都说需要维护第一次和最后一次出现的位置，比如 dr 老师的 PPT，以及 ETT 的原始论文：
Henzinger M R, King V. Randomized fully dynamic graph algorithms with polylogarithmic time per operation[J]. Journal of the ACM (JACM), 1999, 46(4): 502-516.
但是显然不能显式维护，因为进行区间平移的时候，可能有
¶ 代码
jerry3128 大佬的题解里给了 FHQ Treap 的做法，所以我这里给个 splay 的做法吧。
#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;
#define MAXN 10011
struct ETT {
int c[2 * MAXN][2], fa[2 * MAXN];
int ori[MAXN * 2];
// node[v][u] is the occurrence of v after u.
// Corresponds to the directed edge from u to v.
// If u is the parent of v, then it is the first occurrence of v.
// i.e., if u is the parent of v, then uv is the first occurrence of v,
// vu is the last occurrence of v.
unordered_map<int, int> node[MAXN];
stack<int> free_list;
int tot;
inline int& ls(int rt) {
return c[rt][0];
}
inline int& rs(int rt) {
return c[rt][1];
}
inline int side(int x) {
return x == rs(fa[x]);
}
void pushup(int x) {
(void)x;
}
// pushup(x) later
void __rotate_up(int x) {
int y = fa[x], z = fa[y], side_x = side(x), w = c[x][side_x ^ 1];
fa[x] = z;
if (z)
c[z][side(y)] = x;
if (w)
fa[w] = y;
c[y][side_x] = w;
fa[y] = x;
c[x][side_x ^ 1] = y;
pushup(y);
}
void splay(int x, int to = 0) {
while (fa[x] != to) {
int y = fa[x];
if (fa[y] != to)
__rotate_up(side(x) == side(y) ? y : x);
__rotate_up(x);
}
pushup(x);
}
int new_node() {
int x;
if (!free_list.empty()) {
x = free_list.top();
free_list.pop();
} else {
x = ++tot;
}
return x;
}
void del_node(int x) {
free_list.push(x);
}
int __find_min_or_max(int rt, bool mx) {
while (c[rt][mx])
rt = c[rt][mx];
return rt;
}
int find_min_or_max(int rt, bool mx) {
rt = __find_min_or_max(rt, mx);
splay(rt);
return rt;
}
void init(int n) {
for (int i = 1; i <= n; ++i) {
int x = new_node();
ls(x) = rs(x) = fa[x] = 0;
ori[x] = i;
node[i][0] = x;
}
}
void __concat(int x, int y) {
node[ori[y]][ori[x]] = y;
rs(x) = y;
fa[y] = x;
}
void concat(int& x, int& y) {
x = find_min_or_max(x, true);
y = find_min_or_max(y, false);
__concat(x, y);
}
void __append_node(int& x, int y, int u) {
x = find_min_or_max(x, true);
ls(y) = rs(y) = 0;
ori[y] = u;
__concat(x, y);
}
inline void append_node(int& x, int u) {
__append_node(x, new_node(), u);
}
// aAuBa, a is the original root
// Return the splay root(Not the tree root)
int make_root(int u) {
int x = node[u].begin()->second; // Any occurrence
splay(x);
int y = __find_min_or_max(x, false);
if (ori[y] == u)
return x; // Already root
fa[ls(x)] = 0;
ls(x) = 0;
node[u][0] = x;
// y: aA, x: uBa
splay(y);
node[ori[y]].erase(0);
int tmp = y;
y = rs(y);
// y: A
if (y) {
fa[y] = 0;
concat(x, y);
}
// x: uBaA
__append_node(x, tmp, u);
// x: uBaAu
return x;
}
void link(int u, int v) {
int x = node[u].begin()->second; // Any occurrence
int y = make_root(v);
append_node(y, u);
splay(x);
int x2 = rs(x);
y = find_min_or_max(y, false);
node[ori[y]].erase(0);
__concat(x, y);
if (x2) {
fa[x2] = 0;
concat(x, x2);
}
}
void cut(int u, int v) {
make_root(u); // To make sure that u is the father of v
int uv = node[v][u];
node[v].erase(u);
node[v][0] = uv;
auto vu = node[u][v];
node[u].erase(v);
splay(vu);
splay(uv, vu);
int x = ls(uv);
fa[x] = 0;
ls(uv) = 0;
fa[uv] = 0;
// ls(vu) = 0;
int y = rs(vu);
if (y) {
fa[y] = 0;
// rs(vu) = 0;
concat(x, y);
}
del_node(vu);
}
bool in_the_same_splay(int u, int v) {
if (u == v)
return true;
int x = node[u].begin()->second;
splay(x);
int y = node[v].begin()->second;
splay(y);
return fa[x] == y || fa[fa[x]] == y;
}
};
int main() {
int n, m;
static ETT ett;
scanf("%d%d", &n, &m);
ett.init(n);
while (m--) {
static char op[111];
int u, v;
scanf("%s%d%d", op, &u, &v);
switch (op[0]) {
case 'C':
ett.link(u, v);
break;
case 'D':
ett.cut(u, v);
break;
case 'Q':
if (ett.in_the_same_splay(u, v)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}