记录编号	401401	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Cave 洞穴勘测	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.992 s
提交时间	2017-05-02 14:19:21	内存使用	0.54 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define Inf 2e9
const int maxn=15000;
struct Node{
	int tag;
	Node *ch[2],*p;
	inline void retag(){tag^=1;}
	inline void pushup(){;}
	inline void update();
}*null;
Node mem[maxn],*ptr=mem;
inline void Node::update(){
	if(this==null || !tag) return;
	if(ch[0]!=null) ch[0]->retag();
	if(ch[1]!=null) ch[1]->retag();
	swap(ch[0],ch[1]);
	tag=false;
}
inline void newnode(){
	Node *x=ptr++;x->tag=false;
	x->ch[0]=x->ch[1]=x->p=null;
}
inline bool islc(Node *x){
	return x->p->ch[0]==x;
}
inline bool isroot(Node *x){
	return x->p==null || (x->p->ch[0]!=x && x->p->ch[1]!=x);
}
inline void rot(Node *x,int d){
	Node *y=x->ch[d^1];
	if(!isroot(x)) x->p->ch[islc(x)^1]=y;
	y->p=x->p;
	if(y->ch[d]!=null) y->ch[d]->p=x;
	x->ch[d^1]=y->ch[d];
	y->ch[d]=x;
	x->p=y;
	x->pushup();y->pushup();
}
inline void splay(Node *x){
	x->update();
	for(Node *rt=x->p;!isroot(x);rt=x->p){
		if(!isroot(rt)) rt->p->update();
		rt->update();x->update();
		if(isroot(rt)){
			rot(rt,islc(x));
			return;
		}
		if(islc(x)==islc(rt)) rot(rt->p,islc(x));
		else rot(rt,islc(x));
		rot(x->p,islc(x));
	}
}
inline void Access(Node *x){
	Node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		x->pushup();
		y=x;x=x->p;
	}
}
inline void makeroot(Node *x){
	Access(x);splay(x);x->retag();
}
inline void link(Node *x,Node *y){
	makeroot(x);x->p=y;
}
inline void cut(Node *x,Node *y){
	makeroot(x);Access(y);splay(y);
	y->ch[0]=y->ch[0]->p=null;y->pushup();
}
inline Node* Getmin(Node *x){
	while(x->ch[0]!=null)
		x=x->ch[0];
	return x;
}
inline Node* Findroot(Node *x){
	Access(x);splay(x);
	return Getmin(x);
}
inline bool InSame(Node *x,Node *y){
	return Findroot(x)==Findroot(y);
}
int n,m;
void Init();
int main(){
	freopen("sdoi2008_cave.in","r",stdin);
	freopen("sdoi2008_cave.out","w",stdout);
    Init();
    getchar();getchar();
    return 0;
}
void Init(){
	null=ptr++;null->tag=false;
	null->ch[0]=null->ch[1]=null->p=null;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) newnode();
	char op[20];int x,y;
	while(m--){
		scanf(" %s%d%d",op,&x,&y);
		if(op[0]=='C') link(mem+x,mem+y);
		else if(op[0]=='D') cut(mem+x,mem+y);
		else if(op[0]=='Q') {
			if(InSame(mem+x,mem+y)) puts("Yes");
			else puts("No");
		}
	}
}