1. 题目

传送门=￣ω￣=

2. 题解

搞个 lct，实现 link 和 cut 和判断连通性即可。
判断连通性的话，写个 find(x) 函数，返回 x 所在的树的根的编号，判断两个点的 find 值相不相同，相同则联通。

代码：

#include <bits/stdc++.h>
#define NS (10005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;
    while(!isdigit(c))c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int f,s[2],rev;N(){f=s[0]=s[1]=rev=0;}}e[NS];
bool isroot(int a){return e[e[a].f].s[0]!=a&&e[e[a].f].s[1]!=a;}
bool pos(int a){return e[e[a].f].s[1]==a;}
void pdown(int a)
{
    if(!e[a].rev)return;
    e[a].rev=0,e[e[a].s[0]].rev^=1,e[e[a].s[1]].rev^=1;
    swap(e[a].s[0],e[a].s[1]);
}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a);
    if(!isroot(f))e[g].s[pos(f)]=a;
    e[a].f=g,e[f].s[p]=e[a].s[!p],e[a].s[!p]=f,e[f].f=a;
    if(e[f].s[p])e[e[f].s[p]].f=f;
}
int st[NS],top;
void splay(int a)
{
    st[++top]=a;
    for(int i=a;!isroot(i);i=e[i].f)st[++top]=e[i].f;
    while(top)pdown(st[top--]);
    while(!isroot(a))
        if(isroot(e[a].f))rot(a);
        else if(pos(a)^pos(e[a].f))rot(a),rot(a);
        else rot(e[a].f),rot(a);
}
void acc(int a){int b=0;while(a)splay(a),e[a].s[1]=b,b=a,a=e[a].f;}
void evert(int a){acc(a),splay(a),e[a].rev^=1;}
void split(int a,int b){evert(b),acc(a),splay(a);}
void link(int a,int b){evert(a),e[a].f=b;}
void cut(int a,int b){split(a,b),e[a].s[0]=e[b].f=0;}
int find(int a){acc(a),splay(a);while(e[a].s[0])a=e[a].s[0];return a;}
int n,m;
char opt[10];
int main()
{
    IN(n),IN(m);
    for(int i=1,a,b;i<=m;i++)
    {
        scanf("%s",opt),IN(a),IN(b);
        if(opt[0]=='Q'){if(find(a)==find(b))printf("Yes\n");else printf("No\n");}
        else if(opt[0]=='C'){if(find(a)!=find(b))link(a,b);}
        else cut(a,b);
    }
    return 0;
}