BZOJ 2049 Sdoi2008 Cave 洞穴勘測 動態樹 Link-Cut-Tree

BZOJ 2049 Sdoi2008 Cave 洞穴勘測 動態樹 Link-Cut-Tree

題目大意：有一些洞穴，現在都是彼此分開的，將會被一些無向邊所連接。給一些操作，加邊，刪邊，求在某狀態下兩點之間的聯通狀態。

思路：簡單的Link-Cut-Tree維護圖的聯通性。基礎題，建議初學者刷這個。（我才不會說我被坑第一道題刷的2631。。自己調了2天，然後讓同學看2分鐘就看出錯誤了。。。。。。要搞好基礎啊！！！）

判斷兩點是否聯通的時候只要暴力找根比較看看一不一樣就可以了，不會超時。

CODE：

#include 
#include 
#include 
#include 
#define MAX 200010
using namespace std;

struct Complex{
	bool reverse;
	Complex *son[2],*father;

	Complex();
	bool Check() {
		return father->son[1] == this;
	}
	void Reverse() {
		reverse ^= 1;
		swap(son[0],son[1]);
	}
	void PushDown() {
		if(reverse) {
			son[0]->Reverse();
			son[1]->Reverse();
			reverse = false;
		}
	}
}*tree[MAX],*nil = new Complex();

int points,asks;

char c[10];

inline void Splay(Complex *a);
inline void Rotate(Complex *a,bool dir);
inline void Access(Complex *a);
inline void ToRoot(Complex *a);
inline void Link(Complex *x,Complex *y);
inline void Cut(Complex *x,Complex *y);

inline void PushPath(Complex *a);

bool Ask(Complex *x,Complex *y);

int main()
{
	cin >> points >> asks;
	for(int i = 1;i <= points; ++i)
		tree[i] = new Complex();
	for(int x,y,i = 1;i <= asks; ++i) {
		scanf("%s%d%d",c,&x,&y);
		if(c[0] == 'Q')
			printf("%s\n",Ask(tree[x],tree[y]) ? "Yes":"No");
		else if(c[0] == 'C')
			Link(tree[x],tree[y]);
		else
			Cut(tree[x],tree[y]);
	}
	return 0;
}

Complex:: Complex()
{
	father = son[0] = son[1] = nil;
	reverse = false;
}

inline void Splay(Complex *a)
{
	PushPath(a);
	while(a == a->father->son[0] || a == a->father->son[1]) {
		Complex *p = a->father->father;
		if(p->son[0] != a->father && p->son[1] != a->father)
			Rotate(a,!a->Check());
		else if(!a->father->Check()) {
			if(!a->Check())
				Rotate(a->father,true),Rotate(a,true);
			else	Rotate(a,false),Rotate(a,true);
		}
		else {
			if(a->Check())
				Rotate(a->father,false),Rotate(a,false);
			else	Rotate(a,true),Rotate(a,false);
		}
	}
}

inline void Rotate(Complex *a,bool dir)
{
	Complex *f = a->father;
	f->son[!dir] = a->son[dir];
	f->son[!dir]->father = f;
	a->son[dir] = f;
	a->father = f->father;
	if(f->father->son[0] == f || f->father->son[1] == f)
		f->father->son[f->Check()] = a;
	f->father = a;
}

inline void Access(Complex *a)
{
	Complex *last = nil;
	while(a != nil) {
		Splay(a);
		a->son[1] = last;
		last = a;
		a = a->father;
	}
}

inline void ToRoot(Complex *a)
{
	Access(a);
	Splay(a);
	a->Reverse();
}

inline void Link(Complex *x,Complex *y)
{
	ToRoot(x);
	x->father = y;
}

inline void Cut(Complex *x,Complex *y)
{
	ToRoot(x);
	Access(y);
	Splay(y);
	x->father = nil;
	y->son[0] = nil;
}

inline void PushPath(Complex *a)
{
	static Complex *stack[MAX];
	int top = 0;
	for(;a->father->son[0] == a || a->father->son[1] == a;a = a->father)
		stack[++top] = a;
	stack[++top] = a;
	while(top)
		stack[top--]->PushDown();
}

inline bool Ask(Complex *x,Complex *y)
{
	while(x->father != nil)
		x = x->father;
	while(y->father != nil)
		y = y->father;
	return x == y;
}