lp3950 部落冲突

LCT裸题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

inline void Swap(int &A,int &B){
	A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N]; 

inline void updt(int X){
	return;
}
inline void flp(int X){
	Swap(ch[X][0],ch[X][1]);
	rev[X]^=1;
}
inline void pshd(int X){
	if(rev[X]){
		flp(ch[X][0]),flp(ch[X][1]);
		rev[X]=0;
	}
}
inline int ntrt(int X){
	return ch[fa[X]][0]==X||ch[fa[X]][1]==X;
}
inline int fndD(int X){
	return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
	int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(Y),C=ch[X][D^1];
	if(ntrt(Y)){
		ch[Z][D2]=X;
	}
	ch[X][D^1]=Y,ch[Y][D]=C;
	if(C){
		fa[C]=Y;
	}
	fa[Y]=X,fa[X]=Z;
	updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
	int Y=X,Z=0;
	st[++Z]=Y;
	while(ntrt(Y)){
		Y=fa[Y],st[++Z]=Y;
	}
	while(Z){
		pshd(st[Z--]);
	}
	while(ntrt(X)){
		Y=fa[X],Z=fa[Y];
		if(ntrt(Y)){
			splayOne(fndD(X)^fndD(Y)?X:Y);
		}
		splayOne(X);
	}
}
inline void access(int X){
	for(int Y=0;X;Y=X,X=fa[X]){
		splay(X),ch[X][1]=Y,updt(X);
	}
}
inline void chgrt(int X){
	access(X),splay(X),flp(X);
}
inline int qryrt(int X){
	access(X),splay(X);
	while(ch[X][0]){
		pshd(X);
		X=ch[X][0];
	}
	splay(X);
	return X;
}
inline void split(int X,int Y){
	chgrt(X);
	access(Y),splay(Y);
}
inline bool cut(int X,int Y){
	split(X,Y);
	if(ch[Y][0]!=X||ch[X][1]){
		return 0;
	}
	fa[X]=ch[Y][0]=0;
	return 1;
}
inline bool link(int X,int Y){
	chgrt(X);
	if(qryrt(Y)==X){
		return 0;
	}
	fa[X]=Y;
	return 1;
}
int n,m;
int qu[N],qv[N],tp=0;
void init(){
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<=n;++i){
		scanf("%d%d",&u,&v);
		link(u,v);
	}
	char op[4];
	for(int i=1;i<=m;++i){
		cin>>op+1;
		switch(op[1]){
			case 'Q':{
				scanf("%d%d",&u,&v);
				puts(qryrt(u)==qryrt(v)?"Yes":"No");
				break;
			}
			case 'C':{
				scanf("%d%d",&u,&v);
				++tp;
				cut(qu[tp]=u,qv[tp]=v);
				break;
			}
			case 'U':{
				scanf("%d",&u);
				link(qu[u],qv[u]);
				break;
			}
		}
	}
}
int main(){
	init();
	return 0;
}