Link Cut Tree
其实本人觉得LCT对于已经学过树剖与Splay的大佬是很容易理解接受的；
LCT是有树链与Splay结合而成的动态树；什么是动态树呢，就是维护森林的联通性的总称；
先介绍一些概念：
1.prefered child：最后被它的点在x的儿子p节点的子树中，那么p为x的偏爱子节点（相当于树剖中的重儿子）
2.prefered edge：父节点与它的偏爱子节点的边（相当于树剖中的重边）
3.prefered path：由偏爱边连接而成的路径为偏爱路径（相当于树剖中的重链）
我们学LCT时可以发现，每个点只在一条prefered path上，那么这样的话所有的prefered path就可以表示整棵树了，我们可以在每条prefered path 上建一棵splay，关键字为深度
也就是在每棵Splay中，左节点的深度都比当前节点小，右节点的深度都比当前节点深度大；这样，每棵spaly我们把它称作Auxiliary tree（辅助树），每棵辅助树的根节点的父亲
保存与上一棵辅助树的哪个点相连；整棵Splay在原树上相当于一条链（中序遍历）；
原树中的深度是递增的，辅助树中的左右子树是以深度为权值的！
易混点：
原树的根节点！=辅助树中的根节点
原树的左右儿子不等于辅助树的左右儿子
现在来说下一些基本操作：
1.access(x) 访问x节点：切断x与其原先Prefered child 的联系，由于prefered path与prefered child的定义，我们访问一个节点，那么这个点到根节点的所有边都是prefered edge；由于每个点只能有一个prefered child;所以我们需把节点与它原来的prefered child断开，连接这条新的prefered path；先把x splay到根节点，然后更新它的右子节点，直到x的fa 为空；
2.make root(x) access(x）后，splay到根，然后由于权值是深度，所以为了维护左子树权值小于右子树性质，我们还需区间翻转一下；
3.link(x,y) 连边，只需makeroot(x),然后把x的父亲指向y即可；
4.cut（x,y) 删边，先makeroot(x),然后access(y),此时x与y已在同一棵splay中，然后再splay(y),那么x就在y的左儿子中；
最后放下代码：（luogu 3690)
1 #include2 #include 3 #include 4 #define maxn 300233 5 using namespace std; 6 int stack[maxn]; 7 struct hh{ 8 int c[2],fa,val,sum; 9 bool rev; 10 }tree[maxn]; 11 int read(){ 12 int s=0; 13 char c=getchar(); 14 while(c<48||c>57) c=getchar(); 15 while(c>=48&&c<=57){ 16 s=s*10+c-48;c=getchar();} 17 return s; 18 } 19 20 inline void update(int x){ 21 tree[x].sum=tree[tree[x].c[0]].sum^tree[x].val 22 ^tree[tree[x].c[1]].sum; 23 } 24 inline void pushdown(int x){ 25 if(!tree[x].rev) return; 26 int l=tree[x].c[0],r=tree[x].c[1]; 27 if(l) tree[l].rev^=1; 28 if(r) tree[r].rev^=1; 29 swap(tree[x].c[0],tree[x].c[1]); 30 tree[x].rev^=1; 31 } 32 bool isroot(int x){ 33 return tree[tree[x].fa].c[0]!=x&&tree[tree[x].fa].c[1]!=x; 34 } 35 bool get(int x) { 36 return x==tree[tree[x].fa].c[1];} 37 void rotate(int x){ 38 int f=tree[x].fa,ff=tree[tree[x].fa].fa,opt=get(x); 39 tree[f].c[opt]=tree[x].c[opt^1]; 40 tree[tree[x].c[opt^1]].fa=f; 41 if(!isroot(f)) tree[ff].c[get(f)]=x; 42 tree[x].fa=ff;tree[f].fa=x; 43 tree[x].c[opt^1]=f; 44 update(f);update(x); 45 } 46 void splay(int x){ 47 //pushdown(x); 48 int top=0,tmp=x;stack[++top]=x; 49 while(!isroot(tmp))stack[++top]=tree[tmp].fa,tmp=tree[tmp].fa; 50 while(top)pushdown(stack[top]),top--; 51 while(!isroot(x)){ 52 // if(!isroot(tree[x].fa)) rotate(get(tree[x].fa)==get(x)?tree[x].fa:x); 53 // x=tree[x].fa; 54 rotate(x); 55 } 56 } 57 void access(int x){ 58 int son=0; 59 while(x){ 60 splay(x);tree[x].c[1]=son; 61 update(x);son=x;x=tree[x].fa; 62 } 63 } 64 void makeroot(int x){ 65 access(x);splay(x);tree[x].rev^=1; 66 } 67 void link(int x,int y){ 68 makeroot(x);tree[x].fa=y; 69 splay(x); 70 } 71 void cut(int x,int y){ 72 makeroot(x);access(y); 73 splay(y);tree[y].c[0]=tree[x].fa=0; 74 } 75 int query(int x,int y){ 76 makeroot(x);access(y);splay(y); 77 return tree[y].sum; 78 } 79 int getfa(int x){ 80 access(x);splay(x); 81 while(tree[x].c[0]){ 82 pushdown(x);x=tree[x].c[0]; 83 splay(x); 84 } 85 return x; 86 } 87 void change(int x,int y){ 88 makeroot(x); 89 tree[x].val=y; 90 update(x); 91 } 92 int main(){ 93 int n,m,i,x,y,opt; 94 n=read();m=read(); 95 for(i=1;i<=n;i++){ 96 tree[i].val=read(); 97 tree[i].sum=tree[i].val; 98 } 99 while(m--){100 opt=read();x=read();y=read();101 if(opt==0) printf("%d\n",query(x,y));102 else if(opt==1) { if(getfa(x)!=getfa(y))link(x,y);}103 else if(opt==2) { if(getfa(x)==getfa(y)) cut(x,y);}104 else change(x,y);}105 }