题目大意：有三种操作：连接两个洞穴，摧毁两个洞穴的道路，询问两个洞穴是否联通

动态树，可以link和cut，询问的时候判断一下它们的根是否相同就行了

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 10010;
int ch[MAXN][2],pre[MAXN];
int rev[MAXN];
bool rt[MAXN];
void Update_Rev(int r)
{
    if(!r)return;
    swap(ch[r][0],ch[r][1]);
    rev[r] ^= 1;
}
void push_down(int r)
{
    if(rev[r])
    {
        Update_Rev(ch[r][0]);
        Update_Rev(ch[r][1]);
        rev[r] = 0;
    }
}
void Rotate(int x)
{
    int y = pre[x], kind = ch[y][1]==x;
    ch[y][kind] = ch[x][!kind];
    pre[ch[y][kind]] = y;
    pre[x] = pre[y];
    pre[y] = x;
    ch[x][!kind] = y;
    if(rt[y])
        rt[y] = false, rt[x] = true;
    else
        ch[pre[x]][ch[pre[x]][1]==y] = x;
}
void P(int r)
{
    if(!rt[r])P(pre[r]);
    push_down(r);
}
void Splay(int r)
{
    P(r);
    while( !rt[r] )
    {
        int f = pre[r], ff = pre[f];
        if(rt[f])
            Rotate(r);
        else if( (ch[ff][1]==f)==(ch[f][1]==f) )
            Rotate(f), Rotate(r);
        else
            Rotate(r), Rotate(r);
    }
}
int Access(int x)
{
    int y = 0;
    do
    {
        Splay(x);
        rt[ch[x][1]] = true, rt[ch[x][1]=y] = false;
        x = pre[y=x];
    }
    while(x);
    return y;
}
bool judge(int u,int v)
{
    while(pre[u]) u = pre[u];
    while(pre[v]) v = pre[v];
    return u == v;
}
void mroot(int r)
{
    Access(r);
    Splay(r);
    Update_Rev(r);
}
void link(int u,int v)
{
    mroot(u);
    pre[u] = v;
}
void cut(int u,int v)
{
    mroot(u);
    Splay(v);
    pre[ch[v][0]] = pre[v];
    pre[v] = 0;
    rt[ch[v][0]] = true;
    ch[v][0] = 0;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
        for(int i = 0;i <= n;i++)
        {
            pre[i] = 0;
            ch[i][0] = ch[i][1] = 0;
            rev[i] = 0;
            rt[i] = true;
        }
        char op[20];
        int u,v;
        while(m--)
        {
            scanf("%s%d%d",op,&u,&v);
            if(op[0] == 'Q')
            {
                if(judge(u,v))printf("Yes\n");
                else printf("No\n");
            }
            else if(op[0] == 'C')
                link(u,v);
            else cut(u,v);
        }
    return 0;
}