[BZOJ 2049] 동굴 탐사 (SDOI 2008) - LCT 진 · 템 플 릿 문제

테스트 주소: 동굴 탐사
방법: 이 문 제 는 물 을 모 아 볼 수 있다 고 들 었 는데.............................................................
제목 에 따 르 면 그림 은 아무리 변화 해도 숲 이다. 그러면 우 리 는 LCT 의 가장 전형 적 인 용법 을 사용 해 야 한다. 숲 의 유연성 을 유지 해 야 한다.그리고 링크 와 컷 은 템 플 릿 입 니 다. 두 점 사이 의 연관 성 을 측정 하려 면 이 두 점 이 같은 나무 에 있 는 지 확인 하 십시오. (진짜 나 무 는 splay 가 아 닙 니 다.)템 플 릿 에 대해 서 는 저 는 kuangbin 신 번 에 게 배 웠 습 니 다. 빠 르 고 쓰기 도 편 합 니 다.
2 를 범 하 는 곳: splay 때 순환 을 뛰 어 내 리 는 조건 을 적어 라!pre [x] 입 니 다. TLE 가 죽 을 때 까지... pre [x] 가 0 일 때 x 를 진짜 나무의 뿌리 로 표시 하고, rt [x] 가 1 일 때 만 x 를 그 가 있 는 splay 의 뿌리 로 표시 합 니 다.
다음은 본인 코드 입 니 다.

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n,m,ch[10010][2]={0},pre[10010]={0};
bool rev[10010]={0},rt[10010]={0};

void reverse(int x)
{
  rev[x]^=1;
  swap(ch[x][0],ch[x][1]);
}

void pushdown(int x)
{
  if (rev[x])
  {
    reverse(ch[x][0]);
	reverse(ch[x][1]);
	rev[x]=0;
  }
}

void pushup(int x)
{
  
}

void rotate(int x,bool f)
{
  int y=pre[x];
  ch[y][!f]=ch[x][f];
  pre[ch[x][f]]=y;
  ch[x][f]=y;
  if (!rt[y]) ch[pre[y]][ch[pre[y]][1]==y]=x;
  else rt[y]=0,rt[x]=1;
  pre[x]=pre[y];pre[y]=x;
  pushup(y);
}

void Push(int x)
{
  if (!rt[x]) Push(pre[x]);
  pushdown(x);
}

void Splay(int x)
{
  Push(x);
  while(!rt[x])
  {
    if (rt[pre[x]]) rotate(x,ch[pre[x]][0]==x);
	else
	{
	  int y=pre[x],z=pre[pre[x]];
	  bool f=(ch[z][1]==y);
	  if (ch[y][f]==x) rotate(y,!f),rotate(x,!f);
	  else rotate(x,f),rotate(x,!f);
	}
  }
  pushup(x);
}

void access(int x)
{
  int y=0;
  do
  {
    Splay(x);
	rt[ch[x][1]]=1,rt[ch[x][1]=y]=0;
	pushup(x);
	x=pre[y=x];
  }while(x);
}

int find_root(int x)
{
  while(pre[x]) x=pre[x];
  return x;
}

void move(int x)
{
  access(x);
  Splay(x);
  reverse(x);
}

void cut(int x,int y)
{
  move(x);
  Splay(y);
  pre[ch[y][0]]=pre[y];
  pre[y]=0;
  rt[ch[y][0]]=1;
  ch[y][0]=0;
  pushup(y);
}

void link(int x,int y)
{
  move(x);
  pre[x]=y;
}

int main()
{
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++) rt[i]=1;
  
  for(int i=1;i<=m;i++)
  {
    char op[30];
	int x,y;
    scanf("%s%d%d",op,&x,&y);
	if (op[0]=='Q')
	{
	  if (find_root(x)==find_root(y)) printf("Yes
");
	  else printf("No
");
	}
	if (op[0]=='C') link(x,y);
	if (op[0]=='D') cut(x,y);
  }
  
  return 0;
}