记录编号	166257	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Cave 洞穴勘测	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.893 s
提交时间	2015-06-14 18:19:24	内存使用	1.63 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>

#define N 100010
#define l(x) ch[x][0]
#define r(x) ch[x][1]

using namespace std;

int n;

namespace LCT{
	#define isroot(x) ((l(fa[x])!=x && r(fa[x])!=x) || !fa[x])
	
	int ch[N][2],fa[N],rev[N];
	
	void rot(int x,int t){		
		int y=fa[x],z=fa[y];
		if(l(z)==y) l(z)=x;
		if(r(z)==y) r(z)=x;
		fa[x]=z;
		ch[y][t]=ch[x][t^1]; fa[ch[x][t^1]]=y;
		ch[x][t^1]=y; fa[y]=x;
	}
	
	void push(int x){
		if(!rev[x]||!x) return;
		rev[x]=0;
		swap(l(x),r(x));
		if(l(x)) rev[l(x)]^=1;
		if(r(x)) rev[r(x)]^=1;
	}
	
	void splay(int x){
		push(x);
		int z,y;
		while(!isroot(x)){
			y=fa[x],z=fa[y];
			push(z); push(y); push(x);
			rot(x,l(y)==x ? 0:1);
			if(!isroot(x)) rot(x,l(z)==x ? 0:1);
		}
	}
	
	void access(int x){
		int y=0;
		for(;x;x=fa[x])
			splay(x),r(x)=y,y=x;
	}
	
	void makeroot(int x){
		access(x);
		splay(x);
		rev[x]^=1;
	}
	
	void cut(int x,int y){
		makeroot(x);
		access(y);
		splay(y); l(y)=fa[x]=0;
	}
	
	void link(int x,int y){
		makeroot(x);
		fa[x]=y;
	}
	
	int find(int x){
		access(x);
		splay(x);
		for(;l(x);x=l(x)) push(x);
		return x;
	}
}

int m;

int main(){
	freopen("sdoi2008_cave.in","r",stdin);
//	freopen("test.in","r",stdin);
	freopen("sdoi2008_cave.out","w",stdout);
	scanf("%d%d",&n,&m);
	char ch[11];
	for(int i=1,x,y;i<=m;i++){
		scanf("%s%d%d",ch,&x,&y);
	//	printf("%s %d %d\n",ch,x,y);
		if(ch[0]=='C') LCT::link(x,y);
		else if(ch[0]=='D') LCT::cut(x,y);
		else puts(LCT::find(x)==LCT::find(y)?"Yes":"No");
	}
	fclose(stdin);
	fclose(stdout);		
	return 0;
}