记录编号	392989	评测结果	AAAAAAAAAA
题目名称	[SDOI 2008]Cave 洞穴勘测	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.894 s
提交时间	2017-04-09 17:50:45	内存使用	0.49 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <queue>
#include <deque>
#include <list>
using namespace std;
const int MAXN = 1e4+20;
int fa[MAXN], ch[MAXN][2], size[MAXN];
bool rev[MAXN];
inline int getdir(int x){
  return ch[fa[x]][1] == x;
}
inline void link(int x, int y, int d){ //把x放到y的ch[d]上
  if(x)fa[x] = y;
  if(y)ch[y][d] = x;
}
inline bool isroot(int x){
  return ch[fa[x]][getdir(x)] != x;
}
inline void reverse(int x){
  if(x){
    swap(ch[x][1], ch[x][0]);
    rev[x] ^= 1;
  }
}
inline void pushdown(int x){
  if(rev[x]){
    reverse(ch[x][0]); reverse(ch[x][1]);
    rev[x] = 0;
  }
}
inline void pushup(int x){
  size[x] = 1+size[ch[x][0]]+size[ch[x][1]];
}
void rotate(int x){
  int f = fa[x], d = getdir(x);
  fa[x] = fa[f];
  if(!isroot(f))ch[fa[f]][getdir(f)] = x;
  link(ch[x][d^1], f, d);
  link(f, x, d^1);
  pushup(f); pushup(x);
}
void clear(int x){
  if(!isroot(x))clear(fa[x]);
  pushdown(x); //也可以边splay边下推
}
inline void splay(int x){
  for(clear(x); !isroot(x); rotate(x))
    if(!isroot(fa[x]))rotate(getdir(x) == getdir(fa[x])?fa[x]:x);
}
inline void access(int x){
  for(int p = 0; x; x = fa[p = x]){
    splay(x); 
    ch[x][1] = p;
    pushup(x);
  }
}
inline void makeroot(int x){
  access(x); splay(x);
  reverse(x);
}
inline int findroot(int x){
  while(fa[x])x = fa[x];
  return x;
}
inline void link(int u, int v){
  makeroot(u); fa[u] = v;
}
inline void cut(int v){
  access(v);
  splay(v);
  ch[v][0] = fa[ch[v][0]] = 0;
  pushup(v);
}
inline bool isconnect(int u, int v){
  return findroot(u) == findroot(v);
}
int ns[MAXN];
char buf[100];
int main(){
  freopen("sdoi2008_cave.in", "r", stdin);
  freopen("sdoi2008_cave.out", "w", stdout);
  int n, m; scanf("%d %d", &n, &m);
  for(int i = 1; i <= n; i++)ns[i] = i;
  while(m--){
    scanf("%s", buf);
    int x, y; scanf("%d %d", &x, &y);
    if(buf[0] == 'Q'){
      puts(isconnect(ns[x], ns[y])?"Yes":"No");
    }else if(buf[0] == 'D'){
      makeroot(ns[x]);
      cut(ns[y]);
    }else if(buf[0] == 'C'){
      link(ns[x], ns[y]);
    }
  }
  return 0;
}