http://www.zybbs.org/JudgeOnline/problem.php?id=2049

这题莫名其妙R1了……掉RP啊……

这题是维护一个动态森林……乍看是动态树其实真的是动态树……不过这题只要暴力就可以了！难道数据是随机的么？

其实这东西就是一个并查集……但是没有路径压缩（能否按秩合并？）……否则就很难destory了。

Cxy操作：x提根然后将x的父亲设为y。

Dxy操作：x提根，此时y的父亲必为x，所以将y的父亲清空即可。

Qxy操作：x提根，暴力查找y的根是不是x。

如何提根？很简单。把x到根的顺序颠倒过来就可以了。即原来a是b的父亲，让b成为a的父亲。

#include <stdio.h>
#include <string.h>
int n,m,f[10000];
inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline void SetRoot(x){
	int y,t=f[x];
	for(f[x]=-1;(y=t)!=-1;x=y){t=f[y];f[y]=x;}
}main(){
	int ch,x;n=getint();
	memset(f,-1,sizeof(f));
	for(m=getint();m--&&(ch=getchar())>0;){
		SetRoot(x=getint()-1);
		if(ch=='C')f[x]=getint()-1;
		else if(ch=='D')f[getint()-1]=-1;
		else{
			for(ch=getint()-1;ch!=-1&&ch!=x;ch=f[ch]);
			puts(ch==x?"Yes":"No");
		}
	}return 0;
}

用LCT写了下，结果调了5个小时，今天睡觉的时候想到貌似少了个pushdown，结果真的少了个pushdown……

每个操作的执行方法挺多的，我的不是最优的……

首先让Access操作（简称A操作）返回最后一次接上去的时候的父亲，这样A(x)后A(y)返回的就是LCA了。

Q：A(x)后如果A(y)返回x，那么说明LCA是x，显然Yes；否则如果将xSplay到顶后有父亲，说明A(y)时被断掉了，也是Yes；否则No。

D：A(x)后A(y)返回的就是父亲，A(父亲)后splay儿子并将其根设为空

C：最麻烦的操作，为了将x旋到根，A(x)后splay(x)，然后给x打上翻转标记……然后x就是根了（你可以想想为什么），将x的父亲设为y即可。

为了处理翻转标记，一定要弄清楚pushdown的顺序……一开始我在splay里pushdown，但是处理完x再处理fx的话，x可能又上了标记！所以5个小时犯二后我在rot操作里按照ffx,fx,x的顺序pushdown了，TLE->AC……

#include <stdio.h>
#define maxn 10000
typedef struct _Splay{struct _Splay *c[2],*f;_Bool r;}Splay,*PSplay;
Splay null,st[maxn];
inline PSplay fa(PSplay x){return x->f->c[0]==x||x->f->c[1]==x?x->f:&null;}
inline PSplay tran(PSplay x){PSplay t;if(x->r)x->r=0,(t=x->c[0])->r^=1,(x->c[0]=x->c[1])->r^=1,x->c[1]=t;return x;}
inline PSplay node(PSplay x){x->f=x->c[0]=x->c[1]=&null;return x;}
inline PSplay rot(PSplay x){
	PSplay fx=fa(x),ffx=tran(fa(fx));
	_Bool c=tran(fx)->c[1]==x,fc=ffx->c[1]==fx;tran(x);
	if(fx!=&null){
		x->f=fx->f;
		if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx;
		if(ffx!=&null)ffx->c[fc]=x;
		(fx->f=x)->c[!c]=fx;
	}return x;
}inline PSplay splay(PSplay x,PSplay p){
	PSplay fx,ffx;if(x==&null)return x;
	for(;(fx=fa(x))!=p;rot(x))if((ffx=fa(fx))!=p)rot((ffx->c[1]==fx)==(fx->c[1]==x)?fx:x);
	return tran(x);
}inline getint(){
	int re=0,ch=getchar();_Bool k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline PSplay Access(PSplay x){
	PSplay t=&null;
	while(splay(x,&null)->c[1]=t,(x=(t=x)->f)!=&null);
	return splay(t,&null);
}main(){
	int n,i=-1,x,y;
	null.f=null.c[0]=null.c[1]=&null;
	for(n=getint();++i!=n;node(st+i));
	for(n=getint();n--;){
		while((i=getchar())!='Q'&&i!='D'&&i!='C');
		if(i=='Q'){
			Access(st+(x=getint()-1));
			puts(Access(st+(y=getint()-1))!=st+x&&splay(st+x,&null)->f==&null?"No":"Yes");
		}else if(i=='D'){
			Access(st+(x=getint()-1));
			if(Access(st+(y=getint()-1))==st+x){
				Access(st+x);
				splay(st+y,&null)->f=&null;
			}else splay(st+x,&null)->f=&null;
		}else{
			Access(st+(x=getint()-1));
			splay(st+x,&null)->r^=1;
			st[x].f=splay(st+getint()-1,&null);
		}
	}return 0;
}

• inline
• block