树链剖分有多种方法。例如以重量为关键字的重链剖分，以长度为关键字的长链剖分。
而LCT（Link-Cut-Tree）就是一种特殊的利用Splay维护树的剖分结构的算法。
我们称一棵树上连接同一条链的边为实边，连接不同的链的边为虚边，那么这棵树就被分成了许多链。我们称这种剖分方法为实链剖分。
由于实链剖分的虚实是可以动态变化的，因此它具有很多用途。比如动态维护连通性、换根等等操作。
下面我们大致地考虑如何用Splay维护LCT实现实链剖分。
对于实链剖分剖出的每一条链，它总是一条自上往下的链。形式化地说，链中的节点的深度连续且各不相同。
对于原树剖分出的每一条链，我们建一棵Splay维护这棵树。每个点在Splay上的权值是这个点在原树上的深度。这样，无论Splay的结构如何改变，这棵Splay始终维护的是一条链。
对于每棵Splay，我们设它的父亲为整个链的最顶端节点的父亲。
对于原树中的一条实边，由于它位于Splay中，所以它对应着Splay中的一组前驱-后继关系。
对于原树中的一条虚边，它连接的两个节点中的一个节点对应的是两条链之间的连接。位于较下方的那条链对应的Splay的父亲显然指向的是位于较上方的那个节点；而位于较上方的那个节点却不必指向位于较下方的那个节点。这条性质被称为「认父不认子」。
access(Y)
显然，在维护信息的时候，原图上的实链结构并不总是能让我们满意。这时候我们需要从根到Y将树上的某一条竖直的链变成实链，并且不改变它原来的性质。这要怎么做呢？
我们设计一个access（接驳）函数，来完成这个过程。
对于路径上的第一条需要变成实边的虚边，我们是容易找到的——这便是Y所在的Splay的根节点连向其父亲的边。当然，这需要我们将Y旋到其所在的Splay的根。
我们将Y所在的Splay的根的父亲A也旋到其所在的Splay的根，那么它原本的实子链在Splay上正好是它的右子树。所以，我们将它的右子节点改为Y节点。那么，A-Y是已经成为了一条满足操作要求的实链，于是问题就转化为了将A-X转化为实链的子问题。
于是依次向上修改即可。
chgrt(X)
在实际操作中，我们操作的链并不总是从某个节点到根的一条链。这时候我们需要换根操作。
首先，我们将根节点到将要成为根的节点X置于同一条实链上——这可以通过access来达成。
在access后，X便是X所在的Splay中原树深度最浅的节点，也就是最右的节点。这时候，倘若将X旋到其所在的Splay的根，然后翻转X，那么整条链就上下倒转了。
qryrt(X)
在确认连通性的时候，我们需要询问某个点X所在的树的根。
显然，这要求的就是access之后X所在的Splay的最左端节点。
split(X,Y)
在处理具体操作的时候，我们可能会需要将某一条链摘离出来。
如果它们连通，只需要换根到一者，然后access另一者即可。
link(X,Y)
从X到Y连边。
方法很简单，将X作为它所在的树的根，然后直接连一条虚边即可。
cut(X,Y)
删除X和Y之间的边。
倘若保证X和Y之间本来是有连边的，那倒是容易了，直接split出来之后分离两者即可。
现在我们需要考虑两者没有连边的情况。
首先，我们将X变为根，然后寻找Y的根。
考虑Splay操作的影响，我们知道，这样操作之后，在Splay树上，Y节点一定在X节点的右儿子的位置。
在这种情况下，如果Y的根不是X，那么显然两者不连通。如果Y不是X的后继，那么显然两者之间有隔着点，也就不是父子关系。
注意：
一：关于Splay：在LCT中，我习惯使用的SplayOne的方法并不是特别有效，这是因为在LCT中存在虚边。
二：在旋转的时候，需要特别注意判断C是空节点和Y是根节点的情况。在这两种情况下有两句话是不应该写的。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
inline void Swap(int &A,int &B){
A^=B^=A^=B;
}
const int N=300005;
int fa[N],ch[N][2],rev[N],sm[N],val[N];
inline bool isrt(int X){
return ch[fa[X]][0]!=X&&ch[fa[X]][1]!=X;
}
inline void updt(int X){
sm[X]=sm[ch[X][0]]^sm[ch[X][1]]^val[X];
}
inline void flp(int X){
Swap(ch[X][0],ch[X][1]);
rev[X]^=1;
}
inline void pshd(int X){
if(rev[X]){
if(ch[X][0]){
flp(ch[X][0]);
}
if(ch[X][1]){
flp(ch[X][1]);
}
rev[X]=0;
}
}
inline int fndD(int X){
return ch[fa[X]][1]==X;
}
inline void splayOne(int X){
// int D=fndD(X),D2=fndD(fa[X]);
// fa[ch[X][D^1]]=fa[X],ch[fa[X]][D]=ch[X][D^1];
// ch[X][D^1]=fa[X],fa[X]=fa[ch[X][D^1]];
// ch[fa[X]][D2]=X,fa[ch[X][D^1]]=X;
// updt(ch[X][D^1]),updt(X);
// 在LCT中，我习惯使用的SplayOne的方法并不是特别有效，这是因为在LCT中存在虚边。
int Y=fa[X],Z=fa[Y],D=fndD(X),D2=fndD(fa[X]),C=ch[X][D^1];
if(!isrt(Y)){
ch[Z][D2]=X;
}
ch[X][D^1]=Y,ch[Y][D]=C;
if(C){
fa[C]=Y;
}
fa[X]=Z,fa[Y]=X;
updt(Y),updt(X);
}
int st[N];
inline void splay(int X){
int Y=X,Z=0;
st[++Z]=Y;
while(!isrt(Y)){
Y=fa[Y];
st[++Z]=Y;
}
while(Z){
pshd(st[Z--]);
}
while(!isrt(X)){
Y=fa[X],Z=fa[Y];
if(!isrt(Y)){
splayOne((fndD(X)^fndD(Y))?X:Y);
}
splayOne(X);
}
}
inline void access(int X){
for(int Y=0;X;Y=X,X=fa[X]){
splay(X),ch[X][1]=Y,updt(X);
}
}
inline void chgrt(int X){
access(X),splay(X),flp(X);
}
inline int qryrt(int X){
access(X),splay(X);
while(ch[X][0]){
pshd(X);
X=ch[X][0];
}
splay(X);
return X;
}
inline void split(int X,int Y){
chgrt(X);
access(Y),splay(Y);
}
inline bool link(int X,int Y){
chgrt(X);
if(qryrt(Y)==X){
return 0;
}
fa[X]=Y;
return 1;
}
inline bool cut(int X,int Y){
split(X,Y);
if(ch[Y][0]!=X||ch[X][1]){
return 0;
}
fa[X]=ch[Y][0]=0;
return 1;
}
int n,q;
void init(){
scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i){
scanf("%d",&val[i]);
sm[i]=val[i];
}
int op,x,y;
for(int i=1;i<=q;++i){
scanf("%d%d%d",&op,&x,&y);
switch(op){
case 0:{
split(x,y);
printf("%d\n",sm[y]);
break;
}
case 1:{
link(x,y);
break;
}
case 2:{
cut(x,y);
break;
}
case 3:{
splay(x);
val[x]=y;
updt(x);
break;
}
}
}
}
int main(){
init();
return 0;
}