Link-Cut Tree，用来解决动态树问题。
宏观上，LCT维护的是森林而非树。因此存在多颗LCT。有点像动态的树剖（链的确定通过$Access$操作），每条链用一颗$splay$维护。$splay$维护链的关键字是深度，因此一条链的顶端就是$splay$中键值最小的点
由于LCT的资料有很多，在此不详细阐述。只是谈谈理解有困惑的几个点，其中大多已经解决了：
关于虚边
这里的虚边其实不能算叫边，只能说是一个父指针。由于splay是二叉树，但有可能出现有好多虚边指向一个点的情况。因此虚边其实就是儿子认爸爸，而爸爸不认儿子
虚边的真正作用其实是连接每颗splay，换句话说，虚边其实就是每颗splay根节点的父指针，指向另一个splay中的节点。然而这个父指针并不会因为rotate而被破坏，因为这里和普通的splay不同，在rotate的过程是有可能涉及到别的splay中的点（也就是gf），在rotate时，我们一定会把原本指向gf的节点f改为x
关于$Access$操作
Access操作用来让一个节点x到当前LCT的根节点的整条路径都变为实边（并且节点x与下方的实边断开，成为最底部的点）。形象的说，由于每个点只能在一个splay中，有的实边要变为虚边。Access操作时LCT动态维护森林的根本，而之所以能够达到动态效果正是由于实链的不断变换
因此我们可以从x开始向上走，每一次将当前节点（一定是当前splay中深度最大的）splay到根，由于它是深度最大的，一定没有右儿子。因此可以把它的右儿子接上上一轮的splay（第一轮就接上空的）。注意这里的接儿子只需要改变ch的值，而不用更新fa（因为原本是虚边，儿子一定认爸爸）。如果它本身就有右儿子也不管，这样接上另一个儿子之后，原来的儿子依然认它为爸爸，然而爸爸却突然之间不认它了，因此就变成了虚边。
关于$Makeroot$操作
意义就是让节点x成为当前splay的根。因此可以先Access(x)，然后splay(x)（注意splay不会改变任何关系）。此时由于x已经被Access了，因此一定是深度最大的节点。所以splay之后一定没有右儿子。此时想让x成为根，那么也就是深度最小。开始发挥splay最重要的作用——翻转。
说到关于懒标记的，splay中标记的下传可以这样操作（新学）：对于要splay的节点x，先一路递归到达根节点，然后依次往下下传标记。因为splay只会一路影响它的father，update也是一个原理
问题：为什么要整个翻转，而不是只交换根的左右儿子呢？效果貌似一样？虽然实测爆0，但还是不太懂为什么……（我太弱了）
关于$Findroot$操作
找根。最简单的操作之一，先Access和splay，此时最小的便是根
关于$split$操作
提取出x到y的链。只需要makeroot(x)，然后access(y)。此时就打通了x到y的路径（真的好动态哇）。为了方便查找，splay(y)，这样从y一直找最小的就好了。也是灰常简单滴
关于$Link$操作
makeroot(x)，然后把x的父亲置为y
为什么？为什么？为什么？
Update：我可能脑子有点问题…… 其实把x的父亲置为y相当于连了一条虚边——此时他们合并为了一个LCT，其中x就在y的下面了，和正常的一样
关于$Cut$操作
依旧不难。要断x到y的直接边，那么首先要把它提取出来，然后断了就好了。如何提取？split啊！！！
但是注意如果要判断这条边是否存在有两个条件，其一很简单，$ch[y][0]==x?$。因为前面split的时候y被作为了splay的根节点，而因为它们是直接边，所以高度差不超过1.因此就是左儿子
还有一个条件是要满足$ch[x][1]==0$，因为如果x存在右儿子，这个右儿子肯定比它大比y小，这样差值就不是1了
口诀
旋转记得判父亲，伸展记得先下传。
Access记得要更新，Link记得要mroot。
/*By DennyQi 2018*/ #include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; const int MAXN = 300010; const int INF = 0x3f3f3f3f; inline int Max(const int a, const int b){ return (a > b) ? a : b; } inline int Min(const int a, const int b){ return (a < b) ? a : b; } inline int read(){ int x = 0; int w = 1; register char c = getchar(); for(; c ^ '-' && (c < '0' || c > '9'); c = getchar()); if(c == '-') w = -1, c = getchar(); for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w; } int N,M,opt,x,y; int val[MAXN],ch[MAXN][2],fa[MAXN],xr[MAXN],tag[MAXN]; struct LinkCutTree{ inline bool rson(int f, int x){ return ch[f][1] == x; } inline bool isroot(int x){ return ch[fa[x]][rson(fa[x],x)]!=x; } inline void update(int x){ xr[x] = val[x]; if(ch[x][0]) xr[x] ^= xr[ch[x][0]]; if(ch[x][1]) xr[x] ^= xr[ch[x][1]]; } inline void rotate(int x){ int f = fa[x], gf = fa[f]; bool p = rson(f,x), q = !p; if(!isroot(f)) ch[gf][rson(gf,f)] = x; fa[x] = gf; ch[f][p] = ch[x][q], fa[ch[x][q]] = f; ch[x][q] = f, fa[f] = x; update(f), update(x); } void prepare(int x){ if(!isroot(x)) prepare(fa[x]); if(!tag[x]) return; tag[x] = 0; swap(ch[x][0], ch[x][1]); tag[ch[x][0]] ^= 1, tag[ch[x][1]] ^= 1; } inline void splay(int x){ prepare(x); while(!isroot(x)){ int f = fa[x], gf = fa[f]; if(isroot(f)){ rotate(x); break; } if(rson(gf,f) ^ rson(f,x)) rotate(x); else rotate(f); rotate(x); } } inline void access(int x){ for(int y = 0; x; y = x, x = fa[x]){ splay(x), ch[x][1] = y, update(x); } } inline void mroot(int x){ access(x); splay(x); tag[x] ^= 1; } inline int findroot(int x){ access(x); splay(x); while(ch[x][0]) x=ch[x][0]; return x; } inline void split(int x, int y){ mroot(x), access(y), splay(y); } inline void link(int x, int y){ if(findroot(x) == findroot(y)) return; mroot(x); fa[x] = y; } inline void cut(int x, int y){ split(x, y); if(ch[y][0] != x || ch[x][1] != 0) return; ch[y][0] = fa[x] = 0; } inline void change(int x, int y){ mroot(x); val[x] = y; update(x); } }qxz; int main(){ // freopen(".in","r",stdin); N = read(), M = read(); for(int i = 1; i <= N; ++i) val[i] = read(); for(int i = 1; i <= M; ++i){ opt = read(), x = read(), y = read(); if(opt==0) qxz.split(x,y), printf("%d ",xr[y]); if(opt==1) qxz.link(x,y); if(opt==2) qxz.cut(x,y); if(opt==3) qxz.change(x,y); } return 0; }