直接把x设为根,然后查询y所在联通块的根是不是x就行了.
CODE
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<typename T>inline void read(T &num) {
char ch; int flg = 1;
while((ch=getchar())<'0'||ch>'9')if(ch=='-')flg=-flg;
for(num=0;ch>='0'&&ch<='9';num=num*10+ch-'0',ch=getchar());
num*=flg;
}
const int MAXN = 10005;
int n, q;
namespace LCT {
#define ls ch[x][0]
#define rs ch[x][1]
int ch[MAXN][2], fa[MAXN], sz[MAXN];
bool rev[MAXN];
inline bool isr(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
inline bool get(int x) { return x == ch[fa[x]][1]; }
inline void upd(int x) {
sz[x] = sz[ls] + sz[rs] + 1;
}
inline void rot(int x) {
int y = fa[x], z = fa[y], l = get(x), r = l^1;
if(!isr(y)) ch[z][get(y)] = x;
fa[ch[x][r]] = y; fa[y] = x; fa[x] = z;
ch[y][l] = ch[x][r]; ch[x][r] = y;
upd(y), upd(x);
}
inline void mt(int x) { if(rev[x]) rev[x] ^= 1, rev[ls] ^= 1, rev[rs] ^= 1, swap(ls, rs); }
void mtpath(int x) { if(!isr(x)) mtpath(fa[x]); mt(x); }
inline void splay(int x) {
mtpath(x);
for(; !isr(x); rot(x))
if(!isr(fa[x])) rot(get(x)==get(fa[x])?fa[x]:x);
}
inline int access(int x) { int y=0;
for(; x; x=fa[y=x]) splay(x), ch[x][1]=y, upd(x);
return y;
}
inline void bert(int x) { access(x), splay(x), rev[x] ^= 1; }
inline int sert(int x) {
access(x), splay(x);
for(; ch[x][0]; x=ch[x][0]);
return x;
}
inline void link(int x, int y) {
bert(x);
if(sert(y) == x) return;
fa[x] = y;
}
inline void cut(int x, int y) {
bert(x), access(y), splay(y);
if(sert(y) != x || fa[x] != y || ch[x][1] != 0) return;
fa[x] = ch[y][0] = 0; upd(y);
}
inline void modify(int x, int val) {
access(x), splay(x);
ch[x][0] = fa[ch[x][0]] = 0; upd(x);
if(x + val <= n) link(x, x+val);
}
inline int split(int x, int y) {
bert(x), access(y), splay(y);
return y;
}
inline int query(int x, int y) {
bert(x);
return sert(y) == x;
}
}
using namespace LCT;
int main () {
read(n), read(q);
char s[10];
int x, y;
while(q--) {
scanf("%s", s), read(x), read(y);
if(s[0] == 'Q') puts(query(x, y) ? "Yes" : "No");
else if(s[0] == 'C') link(x, y);
else cut(x, y);
}
}