Description
三个操作：1.将两个节点连边。2.将已连边的两个节点之间的边干掉。3.询问两个节点是否联通。保证图从始至终都是一个森林。节点<=10000 操作数<=200000
LCT模板题。
学了一上午EdwardFrog的blog：Cave 洞穴勘测 Link-Cut Tree白话模板，好像了解了一些的样子。
先给原树每一个节点指定一个偏爱儿子（并且这个儿子是你随便指定的，不需要有什么条件），每个父亲连接偏爱儿子的连续的边构成一条链，我们对于每个链维护一颗splay树，使得这颗树的中序遍历的顺序为该链节点按深度递增的顺序。不同的是，这个splay树的根的fa是有值的，其指向维护的链在原树中的深度最浅的点【首端】的父亲节点。
那么大概就是树上的每一个节点的分叉都会使得该节点被另一个维护新的链的splay树指向。然后维护的链的继续分叉，又被别的splay树根指向。。。【P.S.splay树树？？？】
这种维护方式产生了2个借助splay的操作：
1.access(x)：表示将x到根路径的这条链变成一颗splay维护的链。具体方法为：
(1):将x旋转到当前splay的根，丢弃掉右儿子，使得x无偏爱节点，右儿子变成一个分形。
(2):将x指向的fa在其splay树中旋转到根，然后右儿子变成x，原来的右儿子变成一个分形。发现这样使得两颗splay树维护的链合并成了一条结尾为x的链。
(3):递归进行此操作，直到splay的根不再指向节点(splay树的根为原树的根节点)。
2.对于access操作，附加技能：reverse。
由于splay支持区间翻转，我们相当于将x到根节点的链翻转。根据splay树中的中序遍历是按照节点深度递增的性质，以及分叉节点全部利用“偏爱儿子”，从而用别的splay来维护，发现原树直接变成了以x节点为根的树。
注意：标记只对当前splay树生效，分形的splay不参与下传。
那么连边，删边什么的都好说了吧。。。
连边的话，将x节点到根的链提取，然后变成以x为根的splay树，直接令其fa=y。变成了y所在的splay树的一个分形。
删边的话，将树变成以x为根的树，之后将y提取并旋转到根。那么x就在y的左子树中了。
判断所在树是否相同的话，直接找所在的树的根节点判断是否相同就好了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
int read()
{
char ch=getchar(); int re=0;
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9')
re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
return re;
}
struct node
{
node *fa,*c[2];
int tur;
node();
void pushdown();
void reverse(){swap(c[0],c[1]); tur^=1;}
}*null=new node(),*t[10100];
node::node() {fa=c[0]=c[1]=null; tur=0;}
void node::pushdown()
{
if(tur)
{
if(c[0]!=null) c[0]->reverse();
if(c[1]!=null) c[1]->reverse();
tur=0;
}
}
bool isr(node *x){return (x->fa->c[0]!=x)&&(x->fa->c[1]!=x);}
void turnall(node *x)
{
if(!isr(x)) turnall(x->fa);
x->pushdown();
}
void rotate(node *x)
{
if(isr(x)) return ;
node *y=x->fa; int l=(x==y->c[1]),r=l^1;
y->c[l]=x->c[r]; x->c[r]->fa=y;
x->c[r]=y; x->fa=y->fa;
if(!isr(y)) y->fa->c[(y==y->fa->c[1])]=x; y->fa=x;
}
void splay(node *x)
{
turnall(x);
while(!isr(x))
{
node *y=x->fa,*z=y->fa;
if(isr(y)){rotate(x); break;}
if((x==y->c[0])^(y==z->c[0])) rotate(x);
else rotate(y); rotate(x);
}
}
void access(node *x)
{
node *t=null;
while(x!=null)
{
splay(x);
x->c[1]=t;
t=x; x=x->fa;
}
}
void link(node *x,node *y) {access(x); splay(x); x->reverse(); x->fa=y;}
void cut(node *x,node *y)
{
access(x); splay(x); x->reverse();
access(y); splay(y); x->fa=y->c[0]=null;
}
node *find(node *x)
{
access(x); splay(x); while(x->c[0]!=null) x=x->c[0];
return x;
}
void initialize()
{
for(int i=1;i<=n;++i) t[i]=new node();
}
int main()
{
scanf("%d%d",&n,&m);
initialize();
char sw; int x,y;
while(m--)
{
scanf("%s",&sw); x=read(); y=read();
switch(sw)
{
case 'Q':(find(t[x])==find(t[y]))?puts("Yes"):puts("No"); break;
case 'C':link(t[x],t[y]); break;
case 'D':cut(t[x],t[y]); break;
}
}
return 0;
}