【题目链接】
http://www.lydsy.com/JudgeOnline/problem.php?id=2049
【题意】
给定森林，可能有连边或断边的操作，回答若干个连通性的询问。
【思路】
Link-Cut-Tree。
LCT的性质：
1． 有一条重链上的所有节点构成的splay称作这条链的辅助树。
2． 每个点的键值为这个点的深度。
3． 链的辅助树的根的父亲指向链顶的父亲，然而链顶父亲的儿子并不指向链的辅助树的根。
(我会告诉你上面是抄的Popoqqq大爷的PPT么
LCT的操作:
Access：切断原来的重儿子，将结点到原树根的路径变为重路径。先splay到辅助树的根，然后修改右儿子，只用修改ch[1]，右儿子的fa不用改变。
Evert：将u旋转至原树的根，因为执行完Access之后u只是辅助树的根，所以还需要splay至原树根。维护2性质，通过旋转之后u到根的路径反转，需要打上反转标记。
Link：连接两个不相连的节点。将u旋转至原树的根，然后将u的fa设为v。注意这里的操作并不是合并splay而只是连接两棵辅助树。
Cut：断开两个节点。将u旋转至跟，然后Access(v),splay(v)，这时候u一定处于v的左子树，直接切断就行了。
【代码】
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
using namespace std; const int N = 1e5+; struct Node {
Node *ch[],*fa;
int rev;
Node() ;
void reverse() {
rev^=;
swap(ch[],ch[]);
}
void up_push() {
if(fa->ch[]==this||fa->ch[]==this)
fa->up_push();
if(rev) {
ch[]->reverse();
ch[]->reverse();
rev=;
}
}
void maintain() {
}
};
Node *null=new Node,T[N];
Node::Node() { fa=ch[]=ch[]=null; rev=; } void rot(Node* o,int d) { //将o点向上旋转,方向为d^1
Node *p=o->fa;
p->ch[d]=o->ch[d^];
o->ch[d^]->fa=p;
o->ch[d^]=p;
o->fa=p->fa;
if(p==p->fa->ch[])
p->fa->ch[]=o;
else if(p==p->fa->ch[])
p->fa->ch[]=o;
p->fa=o;
p->maintain();
}
void splay(Node* o) { //自下向上旋转至[所属splay]的根
o->up_push();
Node *nf,*nff;
while(o->fa->ch[]==o||o->fa->ch[]==o) { //判断是否是根
nf=o->fa,nff=nf->fa;
if(o==nf->ch[]) {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
} else {
if(nf==nff->ch[]) rot(nf,);
rot(o,);
}
}
o->maintain();
}
void Access(Node* o) {
Node* son=null;
while(o!=null) { //将o到根的路径变为重路径即合并到一棵splay
splay(o);
o->ch[]=son;
o->maintain();
son=o; o=o->fa;
}
}
void evert(Node* o) { //将o转到[整棵动态树]的根
Access(o);
splay(o);
o->reverse();
}
void Link(Node* u,Node* v) {
evert(u);
u->fa=v; //辅助树的根指向链顶的父亲然而链顶的父亲并不指向根
}
void Cut(Node* u,Node* v) {
evert(u);
Access(v),splay(v);
v->ch[]=u->fa=null;
v->maintain();
} int n,m; void query(Node* u,Node* v)
{
Access(u),splay(u);
while(v->fa!=null) v=v->fa;
if(u==v) puts("Yes");
else puts("No");
} int main()
{
// freopen("in.in","r",stdin);
// freopen("out.out","w",stdout);
null->fa=null->ch[]=null->ch[]=null;
char op[]; int u,v;
scanf("%d%d",&n,&m);
while(m--) {
scanf("%s%d%d",&op,&u,&v);
if(op[]=='Q')
query(&T[u],&T[v]);
else if(op[]=='C')
Link(&T[u],&T[v]);
else
Cut(&T[u],&T[v]);
}
return ;
}