传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2049

省选之前来切一道数据结构模板题。

题意

这是一道模板题。

N个点，M次操作，每次加边/删边/询问两个点是否连通，保证每次操作之后仍然是一棵树。

N<=1e4，M<=2e5。

做法

裸的LCT。

需要支持查找一个点所在树的根，只要不断向上查找father就行了。

（fread就是快啊。

#include <bits/stdc++.h>

using namespace std;

const int MAXN=20005, MAXB=2e7;

char BUF[MAXB], *cp=BUF;

void rd(int &x){

	x=0;

	while(*cp<'0'||'9'<*cp) cp++;

	while('0'<=*cp&&*cp<='9') x=x*10+*cp-'0', cp++;

}

char rdc(){

	while(*cp<'A'||'Z'<*cp) cp++;

	return *cp;

}

int N, M, top;

struct Node{

	Node *ch[2], *fa;

	int re;

}nd[MAXN], *rt, *st[MAXN];

inline int isrt(Node *x){return !(x->fa->ch[0]==x||x->fa->ch[1]==x);}

void rot(Node *x){

	Node *y=x->fa, *z=y->fa;

	int l=y->ch[1]==x, r=!l;

	if(!isrt(y)) z->ch[z->ch[1]==y]=x;

	x->ch[r]->fa=y; y->fa=x; x->fa=z;

	y->ch[l]=x->ch[r]; x->ch[r]=y;

}

void down(Node *x){

	if(x->re){

		x->ch[0]->re^=1; x->ch[1]->re^=1;

		swap(x->ch[0], x->ch[1]); x->re=0;

	}

}

void splay(Node *x){

	st[top++]=x;

	for(Node *i=x; !isrt(i); i=i->fa) st[top++]=i->fa;

	for(;top;--top) down(st[top-1]);

	while(!isrt(x)){

		Node *y=x->fa, *z=y->fa;

		if(!isrt(y)) rot((z->ch[1]==y)^(y->ch[1]==x)?x:y);

		rot(x);

	}

}

inline void access(Node *x){

	for(Node *i=nd; x!=nd; i=x,x=x->fa)

		splay(x), x->ch[1]=i;

}

inline void mkrt(Node *x){access(x),splay(x),x->re^=1;}

inline Node *getrt(Node *x){while(x->fa!=nd)x=x->fa; return x;}

inline void lin(Node *x, Node *y){mkrt(x); x->fa=y;}

inline void cut(Node *x, Node *y){

	mkrt(x); access(y); splay(y);

	y->ch[0]=x->fa=nd;

}

int main(){

	fread(BUF, 1, MAXB, stdin);

	rd(N),rd(M);

	for(int i=0; i<=N; ++i) nd[i].ch[0]=nd[i].ch[1]=nd[i].fa=nd;

	for(int i=0,u,v; i<M; ++i){

		char ch=rdc(); rd(u), rd(v);

		if(ch=='Q') puts(getrt(nd+u)==getrt(nd+v)?"Yes":"No");

		else if(ch=='C') lin(nd+u,nd+v);

		else cut(nd+u,nd+v);

	}

	return 0;

}