BZOJ 3282 Tree Link-Cut-Tree 動態樹

BZOJ 3282 Tree Link-Cut-Tree 動態樹

題目大意：維護一種動態樹形數據結構，支持：

1.求樹上兩點之間的點的異或和。

2.連接兩點（不保證不連通）

3.刪除連點之間的邊（不保證兩點聯通）

4.將一個點的點權改成一個值

思路：還是LCT，思路也比較裸。主要是它各種不保證，所以要多加判斷。

CODE：

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

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

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

int points,asks;
int src[MAX];

inline void Rotate(Complex *a,bool dir);
inline void Splay(Complex *a);
inline void PushPath(Complex *a);

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 Modify(Complex *a,int c);
inline int Ask(Complex *x,Complex *y);

inline Complex *FindRoot(Complex *x);

int main()
{
	cin >> points >> asks;
	for(int x,i = 1;i <= points; ++i)
		scanf("%d",&x),tree[i] = new Complex(x);
	for(int flag,x,y,i = 1;i <= asks; ++i) {
		scanf("%d%d%d",&flag,&x,&y);
		if(!flag)	printf("%d\n",Ask(tree[x],tree[y]));
		else if(flag == 1)	Link(tree[x],tree[y]);
		else if(flag == 2)	Cut(tree[x],tree[y]);
		else	Modify(tree[x],y);
	}
	return 0;
}

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;
	f->PushUp();
}

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);
		}
	}	
	a->PushUp();
}

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 void Access(Complex *a)
{
	Complex *last = nil;
	while(a != nil) {
		Splay(a);
		a->son[1] = last;
		a->PushUp();
		last = a;
		a = a->father;
	}
}

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

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

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

inline Complex *FindRoot(Complex *a)
{
	while(a->father != nil)
		a = a->father;
	return a;
}

inline void Modify(Complex *a,int c)
{
	Splay(a);
	a->val = c;
	a->PushUp();
}

inline int Ask(Complex *x,Complex *y)
{
	ToRoot(x);
	Access(y);
	Splay(y);
	return y->_xor;
}