可以按照<Utopiosphere>的调唱出来 “Link-Cut ,Time doesn’t stop .Prepare your doubts ,Eat them up”
参考资料：
1.popoqqq课件
2.《QTREE 解法的一些研究 》
3.http://blog.csdn.net/clove_unique/article/details/50991804
一【理论知识】
Auxiliary Tree(辅助树)
原树与辅助树的关系
辅助树是不断变化的，重链和轻链不断变化
二【实现】
LCT用到的Splay和通常的还是有点不同，没有权值v，不进行查找操作，点编号就是原树的编号
因为是一个Splay森林，多条重链多个根，所以用isRoot(x)判断是否为根，判断isRoot(x)相当于判断x的父亲存不存在
rotate只是设置g的儿子时判断isRoot(f)就行了
splay需要pushDown了(因为没有kth了)，也是判断isRoot(pa)
Access
实现：不断把x splay到当前Atree的根，然后它的右子树就是重儿子了，修改；用y辅助
注意：Access后x不一定为这颗Splay的根，因为中途x变fa了
MakeRoot
实现：Access后splay到根，然后全在x的左子树上(权值是深度)，区间翻转即可
FindRoot
实现：MakeRoot后不断往左找(不需要pushDown因为只是为了判连通性)
Link
实现：MakeRoot(x)然后t[x].fa=y
Cut
实现：MakeRoot(x)然后Access(y) splay(y) ，x就在y的左子树了，t[y].ch[0]=t[x].fa=0;
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; #define pa t[x].fa #define lc t[x].ch[0] #define rc t[x].ch[1] const int N=2e5+5; inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f; } int n,Q,x,y; char s[3]; struct node{ int ch[2],fa,rev,size,w; }t[N]; inline void update(int x){t[x].size=t[lc].size+t[rc].size+t[x].w;} inline int wh(int x){return t[pa].ch[1]==x;} inline int isRoot(int x){return t[pa].ch[0]!=x&&t[pa].ch[1]!=x;} inline void pushDown(int x){ if(t[x].rev){ t[lc].rev^=1; t[rc].rev^=1; swap(lc,rc); t[x].rev=0; } } inline void rotate(int x){ int f=t[x].fa,g=t[f].fa,c=wh(x); if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g; t[f].ch[c]=t[x].ch[c^1];t[t[f].ch[c]].fa=f; t[x].ch[c^1]=f;t[f].fa=x; update(f);update(x); } int st[N],top; inline void splay(int x){ top=0;st[++top]=x; for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa; for(int i=top;i>=1;i--) pushDown(st[i]); for(;!isRoot(x);rotate(x)) if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x); } inline void Access(int x){ int y=0; for(;x;y=x,x=pa){ splay(x); rc=y; } } inline void MakeRoot(int x){ Access(x); splay(x); t[x].rev^=1; } inline int FindRoot(int x){ Access(x); splay(x); while(lc) x=lc; return x; } inline void Link(int x,int y){ MakeRoot(x); t[x].fa=y; //splay(x); } inline void Cut(int x,int y){ MakeRoot(x); Access(y); splay(y); t[y].ch[0]=t[x].fa=0; } int main(){ n=read();Q=read(); while(Q--){ scanf("%s",s);x=read();y=read(); if(s[0]==‘C‘) Link(x,y); else if(s[0]==‘D‘) Cut(x,y); else{ if(FindRoot(x)==FindRoot(y)) puts("Yes"); else puts("No"); } } }
原文：http://www.cnblogs.com/candy99/p/6271344.html