【BZOJ2049】洞穴勘测

    lct,加边的时候需要换根。换根时把其中一个点Splay一下再Reverse一下。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=10010;

struct LCT
{
	struct Node
	{
		Node *c[2],*p,*lcp;
		int rev;
		bool w() {return p->c[1]==this;}
	}*Null,*ID[maxn];

	#define ls x->c[0]
	#define rs x->c[1]

	void Mark_Rev(Node *x) {swap(ls,rs);}

	void Push_Down(Node *x)
	{
		if (x==Null || !x->rev) return;
		Mark_Rev(ls);
		Mark_Rev(rs);
		ls->rev^=1;
		rs->rev^=1;
		x->rev=0;
	}

	void Rotate(Node *x)
	{
		Node *p=x->p;
        bool w=x->w();
        Push_Down(p);Push_Down(x);
        x->lcp=p->lcp;
        p->lcp=Null;
        x->c[!w]->p=p;
        p->p->c[p->w()]=x;
        x->p=p->p;
        p->c[w]=x->c[!w];
        x->c[!w]=p;
        p->p=x;
	}

	void Splay(Node *x)
	{
		if (x==Null) return;
		Push_Down(x);
		while (x->p!=Null)
		{
			if (x->p->p==Null) {Rotate(x);break;}
			if (x->w()==x->p->w()) Rotate(x->p),Rotate(x);
			else Rotate(x),Rotate(x);
		}
		return;
	}

	void Access(Node *x)
	{
		Node *v=Null,*pre=x;
		while (x!=Null)
		{
			Splay(x);
			rs->lcp=x;
			rs->p=Null;
			rs=v;
			v->p=x;
			v->lcp=Null;
			v=x;x=x->lcp;
		}
		Splay(pre);
	}

	Node* Find_Root(Node *x)
	{
		Access(x);
		Splay(x);
		while (ls!=Null) Push_Down(x),x=ls;
		Splay(x);
		return x;
	}

	void Link(Node *x,Node *v)
	{
		Access(x);
		x->rev^=1;
		Mark_Rev(x);
		x->lcp=v;
		Access(x);
	}

	void Cut(Node *x)
	{
		Access(x);
		Splay(x);
		ls->p=Null;
		ls=Null;
		x->lcp=Null;
	}
	
	Node *Prev(Node *x)
	{
		Node *v=ls;
		if (v==Null) return v;
		while (v->c[1]!=Null) Push_Down(v),v=v->c[1];
		return v;
	}

	void Init(int n)
	{
		for (int i=0;i<=n;i++) ID[i]=new Node;
		Null=ID[0];
		for (int i=0;i<=n;i++) ID[i]->rev=0,ID[i]->c[0]=ID[i]->c[1]=ID[i]->p=ID[i]->lcp=Null;
	}

	bool Connected(int x,int y) {return Find_Root(ID[x])==Find_Root(ID[y]);}
	void Connect(int x,int y) {if ((!Connected(x,y))) Link(ID[x],ID[y]);}
	void Destroy(int x,int y)
	{
		Access(ID[x]);
		if (Prev(ID[x])==ID[y]) Cut(ID[x]);
		else Cut(ID[y]);
	}
}T;

inline void read(int &x) {char ch;while ((ch=getchar())<'0' || ch>'9');x=ch-'0';while ((ch=getchar())<='9' && ch>='0') x=x*10+ch-'0';}

char ctr[20];
int n,m;

int main()
{
	read(n),read(m);
	T.Init(n);
	while (m--)
	{
		scanf("%s",ctr);
		int x,y;
		read(x),read(y);
		if (ctr[0]=='Q') if (T.Connected(x,y)) printf("Yes\n");else printf("No\n");
		if (ctr[0]=='C') T.Connect(x,y);
		if (ctr[0]=='D') T.Destroy(x,y);
	}
	return 0;
}