动态树模板（含注释

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#define N 100010
#define int long long
#define lc t[x].ch[0]
#define rc t[x].ch[1]
using namespace std;
int cnt=0, root=0;
char str[N]={0};
struct Node{
   int fa, ls, rs, sum, ch[2], lazy, val;
}t[N<<1];
//川哥说原树其实并没有那么重要,所以维护的基本上都是辅助树的信息
//所有操作并没有直接改原树,但对辅助树的操作相当于是在改原树,怎么说呢有一种对应关系吧
bool isRoot(int s){
   int x = t[s].fa;
   return lc!=s && rc!=s;
}
void reverse(int x){
   if(!x) return ;
   swap(lc, rc);
   t[x].lazy^=1;
}
void pushup(int x){
   t[x].sum = t[x].val^t[lc].sum^t[rc].sum;
}
void pushdown(int x){
   if(t[x].lazy){
      reverse(lc);
	  reverse(rc);
	  t[x].lazy=0;
   }
}
void push(int x){
   if(!isRoot(x)) push(t[x].fa);
   pushdown(x);
}
void rotato(int x){//这段纯纯的splay平衡树旋转
   int y = t[x].fa;
   int z = t[y].fa;
   int k = t[y].ch[1]==x;//x是左儿子还是右儿子
   if(!isRoot(y)) t[z].ch[t[z].ch[1]==y]=x;
   //y是z的左儿子,那第一次转x,y之后,x就是z的左儿子(右儿子同理
   t[x].fa = z;
   t[y].ch[k] = t[x].ch[k^1];
   if(t[x].ch[k^1]) t[t[x].ch[k^1]].fa = y;
   t[y].fa = x;
   t[x].ch[k^1] = y;//这一段真没啥好解释的
   pushup(y);
}
void splay(int x){
   int y, z;
   push(x);
   while(!isRoot(x)){
      y = t[x].fa, z = t[y].fa;
	  if(!isRoot(y))
	     (t[z].ch[0]==y)^(t[y].ch[0]==x) ? rotato(x) : rotato(y);
		 //这很聪明，之字形异或完是1，直线型异或完是0
	  rotato(x);
   }
   pushup(x);
}
void access(int x){
   for(int i=0; x; i=x, x=t[x].fa){
      splay(x);//先把x转到辅助树的树根
	  rc = i;//每次都加到右儿子,然后下次又转到根,那就可以得到一棵只有左儿子的辅助树
	  pushup(x);//说真的我搞不懂什么时候要pushup
   }
}
void makeroot(int x){
   access(x); splay(x); reverse(x);
   //取出根到x的链,把x旋转到平衡树根,全部转到右子树相当于x在原树这段链上深度是最小的,即根
}
int findroot(int x){
   access(x); splay(x); //在辅助树上把x和根放在一个splay,然后把x转到根
   while(lc) pushdown(x), x=lc;
   //你想啊,原树上一条链,根是起点,x是终点,那在splay里面根肯定深度最小,x深度最大
   //而现在x是根,那深度最小的点一定在最左边,即原树上x的根现在在辅助树的最左边
   return x;
}
void split(int x, int y){
   makeroot(x);//把x转到原树的根上
   access(y);//针对原树x到y那条链，在辅助树上把这条链变成一棵splay
   splay(y);//在辅助树上把y转到根
}
void link(int x, int y){
   makeroot(x); t[x].fa = y;
   //先在原树上把x旋转到根,然后把x的爸爸变成y(就行了?
}
void cut(int x, int y){
   split(x, y);//把x到y这条链拎出来,辅助树上弄到一棵splay里
   if(t[y].ch[0]!=x || rc) return ;
   //这里很有说法,现在splay的根是y,然后y是原树x到y这条链最深的点(因为split里面把x变成链头了)
   //所以t[y].ch[0]!=x就是说在原树上x和y根本没有连在一起
   //rc就是说,虽然x在y的左子树,但是x的右儿子是一个深度比x大但是比y小的点,如果存在这种点,那也说明了原树上x和y并不是相邻的
   /*     原树           辅助树
		   y              y
		  /              /
		...    =====>   x
		/              / \
	   x             ..   ..   (x有右儿子)
   */
   t[y].ch[0] = t[x].fa = 0;//原树上切断
   pushup(x);
}
signed main()
{
   freopen("LCT.in","r",stdin);
   freopen("LCT.out","w",stdout);
   int n, m; scanf("%lld%lld", &n, &m);
   for(int i=1; i<=n; ++i){
      scanf("%lld", &t[i].val);
	  t[i].sum = t[i].val;
   }
   while(m--){
      int opt, a, b;
	  scanf("%lld%lld%lld", &opt, &a, &b);
	  if(opt==0){
	     split(a, b); //在辅助树上把a b弄到一棵splay树上，就是针对原树上a到b那一条链
		 printf("%lld\n", t[b].sum);//b被转到了根，而且a到b这条链的信息就是辅助树上b为根的树的信息
	  }
	  if(opt==1){
	  if(findroot(a) != findroot(b))//原树如果a和b不联通
		    link(a, b);
	  }
	  if(opt==2){
	     cut(a, b);//切断a和b的边
	  }
	  if(opt==3){
	     splay(a); t[a].val = b;//把a转到辅助树的根?这是在干嘛
	  }
   }
   return 0;
}