话说都高一了，我居然还不会LCT
于是今天，终于写了第一发LCT，虽然是最简单的，很多操作都没有。。
但总归是我写的第一发。。
话说我在写的是否发现一个很需要注意的地方，就是要注意rotate的时候要判一下不能是根，要不会GG
在bzoj居然是MLE，真奇怪，难道是入栈太多了?
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<stack>
using namespace std;
const int N=30005;
struct node
{int son[2],fa;bool rev;
}s[N];
int n,m;
bool Is_root(int x)
{if((s[s[x].fa].son[0]!=x)&&(s[s[x].fa].son[1]!=x)) return true;return false;
}
void rotate (int x)
{int y=s[x].fa,z=s[y].fa;int r,R,f,w;if (s[y].son[0]==x) w=1;else w=0;r=s[x].son[w];R=y;s[R].son[1-w]=r;if (r!=0) s[r].fa=R;r=x;R=z;if (!Is_root(y)){if (s[R].son[0]==y) s[R].son[0]=r;else s[R].son[1]=r;}if (r!=0) s[r].fa=R;r=y;R=x;s[R].son[w]=r;if (r!=0) s[r].fa=R;
}
void Push_down (int x)
{if(s[x].rev){s[s[x].son[1]].rev^=1; s[s[x].son[0]].rev^=1;swap(s[x].son[0],s[x].son[1]);s[x].rev=0;}
}
stack<int> S;
void Preserve (int x)
{while (!Is_root(x)) S.push(x),x=s[x].fa;S.push(x);while (!S.empty()) Push_down(S.top()),S.pop();
}
void Splay (int x)
{Preserve(x);while (!Is_root(x)){//printf("%d %d %d\n",x,s[x].fa,s[0].son[0]);int y=s[x].fa,z=s[y].fa;if (!Is_root(y)){if ((s[y].son[1]==x)==(s[z].son[1]==y)) rotate(y);else rotate(x);}rotate(x);}
}
void Access (int x)
{int last=0;while (x!=0){Splay(x);s[x].son[1]=last;last=x;x=s[x].fa;}
}
void Make_root (int x)
{Access(x);Splay(x);s[x].rev^=1;
}
void Link (int x,int y)
{Make_root(y);s[y].fa=x;
}
void Split (int x,int y)
{Make_root(x);Access(y);Splay(y);
}
void Cut (int x,int y)
{Split(x,y);s[x].fa=0;s[y].son[0]=0;
}
int Find_root(int x)
{Access(x);
// printf("YES\n");Splay(x);
// printf("NO\n");while (s[x].son[0]!=0) {x=s[x].son[0];}return x;
}
int main()
{scanf("%d%d",&n,&m);for (int u=1;u<=n;u++) s[u].son[0]=s[u].son[1]=0,s[u].fa=0;while (m--){char ss[15];int x,y;scanf("%s%d%d",ss,&x,&y);if (ss[0]=='C')//建边Link(x,y); else if (ss[0]=='D')Cut(x,y);else{if (Find_root(x)==Find_root(y)) printf("Yes\n");else printf("No\n");}}return 0;
}