提交记录

#include<iostream>
using namespace std;
const int N(1e4+5);
int n,m;
int fa[N],ch[N][2],stk[N];
bool tag[N];
inline bool isroot(int x){
	return (ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x);
}
inline void reverse(int x){
	swap(ch[x][0],ch[x][1]);tag[x]^=1;
}
inline void pushdown(int x){
	if(tag[x]){
		if(ch[x][0]) reverse(ch[x][0]);
		if(ch[x][1]) reverse(ch[x][1]);
		tag[x]=0;
	}
}
inline void rotate(int x){
	int y=fa[x],z=fa[y],k=(ch[y][1]==x);
	if(!isroot(y)) ch[z][ch[z][1]==y]=x;
	fa[x]=z;
	ch[y][k]=ch[x][k^1];
	if(ch[x][k^1]) fa[ch[x][k^1]]=y;
	ch[x][k^1]=y;
	fa[y]=x;
}
inline void splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(!isroot(y)) stk[++top]=y=fa[y];
	while(top) pushdown(stk[top--]);
	while(!isroot(x)){
		y=fa[x];
		if(!isroot(y))
			rotate((ch[y][1]==x)^(ch[fa[y]][1]==y)?x:y);
		rotate(x);
	}
}
inline void access(int x){
	for(int y=0;x;y=x,x=fa[x])
		splay(x),ch[x][1]=y;
}
inline void makeroot(int x){
	access(x);splay(x);reverse(x);
}
inline int findroot(int x){
	access(x);splay(x);
	while(ch[x][0]) pushdown(x),x=ch[x][0];
	splay(x);
	return x;
}
inline void link(int x,int y){
	makeroot(x);fa[x]=y;
}
inline void cut(int x,int y){
	makeroot(x);fa[y]=ch[x][1]=0;
}
int main(){
	#ifdef ytxy
	freopen("in.txt","r",stdin);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	while(m--){
		char op[15];
		int u,v;
		cin>>op>>u>>v;
		if(op[0]=='C'){
			if(u==v) continue;
			link(u,v);
		}
		else if(op[0]=='D'){
			if(u==v) continue;
			cut(u,v);
		}
		else if(op[0]=='Q'){
			if(findroot(u)==findroot(v)) cout<<"Yes\n";
			else cout<<"No\n";
		}
	}
}