模板

LCT

LCT中最主要的是$Access$操作，$Access(u)$操作的含义是，从当前的节点u向他所在的根节点连一条重路径，这是相当于把沿路的重路径全都断开，重新拉一条从u到根的重路径。

$makeroot(x)$操作：

若想让u成为当前树的根节点，则可以先$access(u)$，再$splay(u)$，把u转为当前splay的根节点。因为splay维护的是深度，所以u没有右儿子（没有比u还要深的点，因为重链定义），所以换根就相当于一次区间翻转，交换左右子树即完成区间翻转。此时就可以打标记了。

所以，$makeroot=access+splay+rev$

还有一个$isroot$操作，就是判断这是不是一条重路径的根，只要他的fa指针指向的节点的左右子树都不是他（证明此时这是一条虚边），那么这就是一棵子树的根节点。

$link(x,y)$操作：

在u和v之间连边，可以$makeroot(u)$，再让$u$的父亲为$v$，这就相当于$v$本身是一棵$splay$，而$u$和$v$之间连了条轻边。

$cut(u,v)$操作：

断开$u$和$v$之间的边，可以先$makeroot(u)$，再$access(v)$，再$splay(v)$，此时$v$的左儿子必定为$u$，于是断开$v$和$v$的左儿子即可。

至于翻转标记的传递，就是跟$Splay$一样就行了。

但标记下放有一个问题。因为$splay$是时时刻刻在分裂与合并的，因为要动态维护每条重链，所以在$splay$之前，要先把根节点到当前节点全部下放一遍标记，防止标记下放不完全。

$split(x,y)$操作：

$split$相当于把两个子树分开，考虑到我们$cut$的时候第一步也是分开，所以$split=makeroot(u)+access(v)+splay(v)$

然后还要保存一些轻边（虚边），对于轻边我们需要单独记录处理。在原树上，当前重链的顶端节点与他的父亲的边即为轻边，如果不记录，树将是不完整的。

具体到代码实现，可以是当前$splay$的根节点的父亲即为当前$splay$上面的那个重链所在的$splay$上的点，但上面的$splay$的儿子并不指向当前$splay$的父亲，即为用$splay$的根节点的父亲来存储轻边。

动态树的主要时间消耗在$Access$上，而$Access$的时间复杂度是$O(nlogn)$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 300000+9
using namespace std;
int n,m;
int val[MAXN],xr[MAXN];
int son[MAXN][2];
int fa[MAXN],rev[MAXN],xorsum[MAXN];
bool isroot(int x){
    int y=fa[x];
    if(son[y][0]!=x && son[y][1]!=x)
        return true;
    return false;
}
void update(int x){
    xr[x]=val[x]^xr[son[x][0]]^xr[son[x][1]];
}
void pushdown(int x){
    int ls=son[x][0],rs=son[x][1];
    if(rev[x]){
        rev[ls]^=1;
        rev[rs]^=1;
        rev[x]^=1;
        swap(son[x][0],son[x][1]);
    }
}
void rotate(int x){
    int y=fa[x],z=fa[y];
    int tmp1,tmp2;
    tmp1= son[y][0]==x ? 0 : 1;
    tmp2=tmp1^1;
    if(!isroot(y)){
        if(son[z][0]==y)
            son[z][0]=x;
        else
            son[z][1]=x;
    }
    fa[x]=z;
    fa[y]=x;
    fa[son[x][tmp2]]=y;
    son[y][tmp1]=son[x][tmp2];
    son[x][tmp2]=y;
    update(y);
    update(x);
}
int sta[MAXN];
void splay(int x){
    int top=1;
    sta[top]=x;
    int i;
    for(i=x; !isroot(i) ;i=fa[i]) sta[++top]=fa[i];
    while(top)
        pushdown(sta[top--]);
    while(!isroot(x)){
        int y=fa[x],z=fa[y];
        if(!isroot(y)){
            if((son[y][0]==x)^(son[z][0]==y))
                rotate(x);
            else
                rotate(y);
        }
        rotate(x);
    }
}
void access(int x){
    int i;
    for(i=0;x;i=x,x=fa[x]){
        splay(x);
        son[x][1]=i;
        update(x);
    }
}
void makeroot(int x){
    access(x);
    splay(x);
    rev[x]^=1;
}
void Link(int x,int y){
    makeroot(x);
    fa[x]=y;
}
void split(int x,int y){
    makeroot(x);
    access(y);
    splay(y);
}
void Cut(int x,int y){
    split(x,y);
    if(son[y][0]==x){
        son[y][0]=0;
        fa[x]=0;
    }
}
int FindFather(int x){
    access(x);
    splay(x);
    while(son[x][0])
        x=son[x][0];
    return x;
}
void solve(){
    int i;
    int opt,x,y;
    for(i=1;i<=m;i++){
        scanf("%d",&opt);
        if(opt==0){
            scanf("%d%d",&x,&y);
            split(x,y);
            printf("%d\n",xr[y]);
        }
        if(opt==1){
            scanf("%d%d",&x,&y);
            int xx=FindFather(x);
            int yy=FindFather(y);
            if(xx!=yy)
                Link(x,y);
        }
        if(opt==2){
            scanf("%d%d",&x,&y);
            int xx=FindFather(x);
            int yy=FindFather(y);
            if(xx==yy)
                Cut(x,y);
        }
        if(opt==3){
            scanf("%d%d",&x,&y);
            access(x);
            splay(x);
            val[x]=y;
            update(x);
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int i;
    for(i=1;i<=n;i++){
        scanf("%d",&val[i]);
        xr[i]=val[i];
    }
    solve();
    return 0;
}