题目大意：有$n$个洞穴，$m$条指令，指令有三种

1. $Connect\;u\;v$：在$u,v$之间连一条边
2. $Destroy\;u\;v$：切断$u,v$之间的边
3. $Query\;u\;v$：询问$u,v$是否连通

（数据保证合法）

题解：$LCT$（潘佳奇的板子）

卡点：无（潘佳奇的板子）

C++ Code：

#include 
     
      #include 
      
       #define maxn 10010using 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;}