题目大意：有$n$个洞穴，$m$条指令，指令有三种
- $Connect;u;v$：在$u,v$之间连一条边
- $Destroy;u;v$：切断$u,v$之间的边
- $Query;u;v$：询问$u,v$是否连通
（数据保证合法）
题解：$LCT$（潘佳奇的板子）
卡点：无（潘佳奇的板子）
C++ Code：
#include <cstdio>
#include <cstring>
#define maxn 10010
using namespace std;
int son[2][maxn], fa[maxn], tg[maxn];
inline bool get(int x, int flag = 1) {return son[flag][fa[x]] == x;}
inline bool is_root(int x) {return !(get(x, 0) || get(x, 1));}
inline void swap(int &x, int &y) {x ^= y ^= x ^= y;}
inline void rotate(int x) {
int y = fa[x], z = fa[y]; bool b = get(x);
if (!is_root(y)) son[get(y)][z] = x;
son[b][y] = son[!b][x]; son[!b][x] = y;
fa[y] = x; fa[x] = z; fa[son[b][y]] = y;
}
inline void pushdown(int x) {
if (tg[x]) {
tg[son[0][x]] ^= 1; tg[son[1][x]] ^= 1;
swap(son[0][x], son[1][x]); tg[x] ^= 1;
}
}
int st[maxn], top;
inline void splay(int x) {
st[top = 1] = x;
for (int y = x; !is_root(y); st[++top] = y = fa[y]);
for (; top; --top) if (tg[st[top]]) pushdown(st[top]);
for (; !is_root(x); rotate(x)) if (!is_root(fa[x]))
get(x) ^ get(fa[x]) ? rotate(x) : rotate(fa[x]);
}
inline void access(int x) {for (int t = 0; x; son[1][x] = t, t = x, x = fa[x]) splay(x);}
inline void make_root(int x) {access(x); splay(x); tg[x] ^= 1;}
inline void split(int x, int y) {make_root(x); access(y); splay(y);}
inline void link(int x, int y) {make_root(x); fa[x] = y;}
inline void cut(int x, int y) {split(x, y); son[0][y] = fa[x] = 0;}
inline bool query(int x, int y) {
split(x, y); int now = y;
while (son[0][now]) now = son[0][now];
return now == x;
}
int n, Q, x, y;
char s[30];
int main() {
scanf("%d%d", &n, &Q);
while (Q --> 0) {
scanf("%s%d%d", s, &x, &y);
if (s[0] == 'Q') {
if (query(x, y)) puts("Yes");
else puts("No");
} else {
if (s[0] == 'C') link(x, y);
else cut(x, y);
}
}
return 0;
}