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 = ;
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 = ; int w = ; register char c = getchar();
for(; c ^ '-' && (c < '' || c > ''); c = getchar());
if(c == '-') w = -, c = getchar();
for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - ''; return x * w;
}
int N,M,opt,x,y;
int val[MAXN],ch[MAXN][],fa[MAXN],xr[MAXN],tag[MAXN];
struct LinkCutTree{
inline bool rson(int f, int x){
return ch[f][] == 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][]) xr[x] ^= xr[ch[x][]];
if(ch[x][]) xr[x] ^= xr[ch[x][]];
}
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] = ;
swap(ch[x][], ch[x][]);
tag[ch[x][]] ^= , tag[ch[x][]] ^= ;
}
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 = ; x; y = x, x = fa[x]){
splay(x), ch[x][] = y, update(x);
}
}
inline void mroot(int x){
access(x);
splay(x);
tag[x] ^= ;
}
inline int findroot(int x){
access(x);
splay(x);
while(ch[x][]) x=ch[x][];
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][] != x || ch[x][] != ) return;
ch[y][] = fa[x] = ;
}
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 = ; i <= N; ++i) val[i] = read();
for(int i = ; i <= M; ++i){
opt = read(), x = read(), y = read();
if(opt==) qxz.split(x,y), printf("%d\n",xr[y]);
if(opt==) qxz.link(x,y);
if(opt==) qxz.cut(x,y);
if(opt==) qxz.change(x,y);
}
return ;
}