记录编号	399584	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Cave 洞穴勘测	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.794 s
提交时间	2017-04-27 07:47:00	内存使用	0.44 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define isroot(x) ((x)->p==null||((x)!=(x)->p->ch[0]&&(x)!=(x)->p->ch[1]))
#define dir(x) ((x)==(x)->p->ch[1])
using namespace std;
const int maxn=10010;
struct node{
	bool rev;
	node *ch[2],*p;
	node():rev(false){}
	inline void pushdown(){
		if(!rev)return;
		ch[0]->rev^=true;
		ch[1]->rev^=true;
		swap(ch[0],ch[1]);
		rev=false;
	}
}null[maxn];
node *access(node*);
void makeroot(node*);
void link(node*,node*);
void cut(node*,node*);
node *getroot(node*);
void splay(node*);
void rot(node*,int);
char c[15];
int n,m;
int main(){
	freopen("sdoi2008_cave.in","r",stdin);
	freopen("sdoi2008_cave.out","w",stdout);
	null->ch[0]=null->ch[1]=null->p=null;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)null[i].ch[0]=null[i].ch[1]=null[i].p=null;
	while(m--){
		int x,y;
		scanf("%s%d%d",c,&x,&y);
		if(*c=='C')link(null+x,null+y);
		else if(*c=='D')cut(null+x,null+y);
		else printf(getroot(null+x)==getroot(null+y)?"Yes\n":"No\n");
	}
	return 0;
}
node *access(node *x){
	node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		y=x;
		x=x->p;
	}
	return y;
}
void makeroot(node *x){
	access(x);
	splay(x);
	x->rev^=true;
}
void link(node *x,node *y){
	makeroot(x);
	x->p=y;
}
void cut(node *x,node *y){
	makeroot(x);
	access(y);
	splay(y);
	y->ch[0]->p=null;
	y->ch[0]=null;
}
node *getroot(node *x){
	x=access(x);
	while(x->pushdown(),x->ch[0]!=null)x=x->ch[0];
	splay(x);
	return x;
}
void splay(node *x){
	x->pushdown();
	while(!isroot(x)){
		if(!isroot(x->p))x->p->p->pushdown();
		x->p->pushdown();
		x->pushdown();
		if(isroot(x->p)){
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
inline void rot(node *x,int d){
	node *y=x->ch[d^1];
	if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x;
	y->p=x->p;
	if(!isroot(x))x->p->ch[dir(x)]=y;
	(y->ch[d]=x)->p=y;
}