评测时mle了 但是在洛谷在线IDE上没有

运行成功 62ms 616kb

评测记录 https://www.luogu.com.cn/record/47907440

代码

#include<iostream>
#include<algorithm>
#include<cstdio>
#define N 10010
using namespace std;
int ch[N][2],fa[N];
bool tag[N];
int n,m,x,y;
char tt[20];
void pushdown(int x)
{
	if(x&&tag[x]==1)
	{
		tag[ch[x][0]]^=1;
		tag[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);
	}
}
bool isroot(int x)
{
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
bool son(int x)
{
	if(x==ch[fa[x]][0]) return 0;
	else return 1;
}
void rotate(int x)
{
	int y=fa[x];
	int zch=ch[x][!son(x)];
	int gr=fa[y];
	bool yy=son(y),xx=son(x);
	if(!isroot(y)) ch[gr][yy]=x;fa[x]=gr;
	ch[x][!xx]=y;fa[y]=x;
	ch[y][xx]=zch;fa[zch]=y;
}
void cleartag(int x)
{
	if(isroot(x))
	{
		pushdown(x);
		return;
	}
	cleartag(fa[x]);
	pushdown(x);
}
void splay(int x)
{
	cleartag(x);
	while(!isroot(x))
	{
		int fat=fa[x];
		int gaf=fa[fat];
		if(isroot(fat)) rotate(x);
		else
			if(son(fat)==son(x)) {rotate(fat);rotate(x);}		
			else{rotate(x);rotate(x);}
	}
}
void access(int x)
{
	int tmp=x;
	for(int t=0;x;x=fa[t=x])
		splay(x),ch[x][1]=t;
	splay(tmp);
}
void makeroot(int x)
{
	access(x);
	tag[x]^=1;	
}
void link(int x,int y)
{
	makeroot(x);
	fa[x]=y;
}
void cut(int x,int y)
{
	makeroot(x);
	access(y);
	fa[x]=ch[y][0]=0;
}
int find(int x)
{
	for(access(x);ch[x][0];x=ch[x][0]);
	return x;
}
int main()
{
	scanf("%d%d",&n,&m);
	while(m--)
	{
		scanf("%s%d%d",tt,&x,&y);
		if(tt[0]=='C') link(x,y);
		if(tt[0]=='D') cut(x,y);
		if(tt[0]=='Q')
			if(find(x)==find(y))
				printf("Yes\n");
			else
				printf("No\n");
	}
	return 0;
}