学步园

Link-Cut-Tree详细解释看这里 Link/cut tree From Wikipedia, the free encyclopedia .

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 10005
#define inf 0x3f3f3f3f

struct splay
{
	splay *fa,*ch[2];
	int v,rev;
	splay(int val=0)
	{
		v=val; rev=0;
	}
	inline bool root()
	{
		return fa->ch[1]!=this&&fa->ch[0]!=this;
	}
	inline int check()
	{
		return fa->ch[1]==this;
	}
	inline void combine(splay *x,int d)
	{
		ch[d]=x; x->fa=this;
	}
	void pushdown()
	{
		if(!root()) fa->pushdown();
		if(rev) reverse();
	}
	inline void reverse()
	{
		rev^=1;
		swap(ch[0],ch[1]);
		ch[0]->rev^=1; ch[1]->rev^=1;
	}
}*null=new splay(),*tree[N];

inline void rotate(splay *x)
{
	splay *k=x->fa;
	int d=!x->check();
	k->combine(x->ch[d],d^1);
	if(!k->root()) k->fa->ch[k->check()]=x;
	x->fa=k->fa;
	x->combine(k,d);
}

inline void Splay(splay *x)
{
	x->pushdown();
	while(!x->root())
	{
		if(!x->fa->root())
			rotate(x->check()^x->fa->check()?x:x->fa);
		rotate(x);
	}
}

void access(splay *x)
{
	splay *now=x,*pre=null;
	while(now!=null)
		Splay(now), now->ch[1]=pre,
		pre=now, now=now->fa;
	Splay(x);
}

void make_root(splay *x)
{
	access(x);
	x->rev^=1;
}

void link(splay *x,splay *y)
{
	make_root(x);
	x->fa=y;
}

void cut(splay *x,splay *y)
{
	make_root(x);
	access(y);
	x->fa=y->ch[0]=null;
}

int find_root(splay *x)
{
	access(x);
	while(x->ch[0]!=null)
		x=x->ch[0];
	return x->v;
}

int n,m;

int main()
{
	cin>>n>>m;
	char str[5];int u,v;
	for(int i=1;i<=n;i++)
		tree[i]=new splay(i),
		tree[i]->fa=tree[i]->ch[0]=tree[i]->ch[1]=null;
	while(m--)
	{
		scanf("%s%d%d",str,&u,&v);
		switch(str[0])
		{
			case 'C': link(tree[u],tree[v]); break;
			case 'D': cut(tree[u],tree[v]); break;
			case 'Q': puts(find_root(tree[u])==find_root(tree[v])?
						"Yes":"No"); break;
		}
	}
}