【题目描述】

（太长也懒得复制了）

题目大意就是：给你N个点，这N个点一开始没有路径相连，然后给出M个操作，包含三个操作：

1.Query(x,y)：询问x，y之间是否连通。

2.Connect(x,y)：在x,y之间连一条边。

3.Destroy(x,y)：将x,y之间的边删除。

最后对于每个Query，如果连通就输出"Yes"，否则输出“No”。

【输入格式】

第一行为两个正整数n和m，分别表示洞穴的个数和终端机上出现过的指令的个数。以下m行，依次表示终端机上出现的各条指令。每行开头是一个表示指令种类的字符串s（"Connect”、”Destroy”或者”Query”，区分大小写），之后有两个整数u和v (1≤u, v≤n且u≠v) 分别表示两个洞穴的编号。

【输出格式】

对每个Query指令，输出洞穴u和洞穴v是否互相连通：是输出”Yes”，否则输出”No”。（不含双引号）

【样例输入】

Connect 1 2

Connect 3 1

Query 2 3

Destroy 1 3

Query 2 3

【样例输出】

Yes

No

【备注】

10%的数据满足n≤1000, m≤20000

20%的数据满足n≤2000, m≤40000

30%的数据满足n≤3000, m≤60000

40%的数据满足n≤4000, m≤80000

50%的数据满足n≤5000, m≤100000

60%的数据满足n≤6000, m≤120000

70%的数据满足n≤7000, m≤140000

80%的数据满足n≤8000, m≤160000

90%的数据满足n≤9000, m≤180000

100%的数据满足n≤10000, m≤200000

保证所有Destroy指令将摧毁的是一条存在的通道

本题输入、输出规模比较大，建议c\c++选手使用scanf和printf进行I\O操作以免超时

【题目分析】

很裸的一道LCT题，命令只包含findroot、link、cut操作（但还是要把操作写完QAQ）

【代码~】

#include
    
     using namespace std;const int MAXN=1e4+10;int n,m,u,v,qr,que[MAXN];struct node{	int fa,lc,rc;	int rev;}tr[MAXN];bool which(const int &x){	return tr[tr[x].fa].rc==x;}bool isroot(const int &x){	if(!tr[x].fa)	  return true;	return tr[tr[x].fa].lc!=x&&tr[tr[x].fa].rc!=x;}void push_down(const int &root){	if(tr[root].rev)	{		swap(tr[root].lc,tr[root].rc);		if(tr[root].lc)		  tr[tr[root].lc].rev^=1;		if(tr[root].rc)		  tr[tr[root].rc].rev^=1;		tr[root].rev=0;	}}void rotate(const int &x){	int y=tr[x].fa,z=tr[y].fa,b=tr[y].lc==x?tr[x].rc:tr[x].lc;	if(z&&!isroot(y))	  (tr[z].lc==y?tr[z].lc:tr[z].rc)=x;	tr[x].fa=z,tr[y].fa=x,b?tr[b].fa=y:0;	if(tr[y].lc==x)	  tr[x].rc=y,tr[y].lc=b;	else	  tr[x].lc=y,tr[y].rc=b;}void splay(const int &x){	que[qr=0]=x;	for(int y=x;!isroot(y);y=tr[y].fa)	  que[++qr]=tr[y].fa;	for(int i=qr;i>=0;--i)	  push_down(que[i]);	while(!isroot(x))	{		if(!isroot(tr[x].fa))		{			if(which(x)==which(tr[x].fa))			  rotate(tr[x].fa);			else			  rotate(x);		}		rotate(x);	}}void access(int x){	for(int y=0;x;y=x,x=tr[x].fa)	{		splay(x);		tr[x].rc=y;		if(y)		  tr[y].fa=x;	}}int findroot(int x){	access(x);	splay(x);	while(push_down(x),tr[x].lc)	  x=tr[x].lc;	splay(x);	return x;}void makeroot(int x){	access(x);	splay(x);	tr[x].rev=1;}void link(const int &x,const int &y){	makeroot(x);	tr[x].fa=y;}void cut(const int &x,const int &y){	makeroot(x);	access(y);	splay(y);	tr[y].lc=0;	tr[x].fa=0;}int Read(){	int i=0,f=1;	char c;	for(c=getchar();(c>'9'||c<'0')&&c!='-';c=getchar());	if(c=='-')	  f=-1,c=getchar();	for(;c>='0'&&c<='9';c=getchar())	  i=(i<<3)+(i<<1)+c-'0';	return i*f;}int main(){	scanf("%d%d",&n,&m);	char ch;	for(int i=1;i<=m;++i)	{		while(ch=getchar(),ch>'Z'||ch<'A');		if(ch=='Q')		{			if(findroot(Read())==findroot(Read()))			  printf("Yes\n");			else			  printf("No\n");		}		else		{			if(ch=='C')			  link(Read(),Read());			else			  cut(Read(),Read());		}	}	return 0;}