关于 LCT(Link-Cut-Tree)

说难不难，总归是个板子；说简单也不简单，写法千变万化。总的来说就是把板子背熟，才能在考场上写的出来（但是貌似写的出来也看不出来 (～￣▽￣)～ ）

下面说说各个函数的作用：

notroot：判断点x是不是其所在(实)链的顶点(根，亦或称在当前LCT中深度最小的点)

pushr：翻转操作(其实就是个推标记的)

pushup:将节点信息上传(一般是维护的信息)

pushdown：将节点信息下放(一般是标记)

rot、splay：。。。不要告诉我你不认识

access：打通点x到当前LCT的根的一条实链

makeroot：将x变为LCT的根

findroot：寻找原树的根

link：连接两个点

cut：切断一条连边

#include <algorithm> //STL通用算法
#include <cmath> //定义数学函数
#include <cstdio> //定义输入/输出函数
#include <iostream> //数据流输入/输出
#include <cstring> //字符串处理
#include <string> //字符串类
#include <ctime> //定义关于时间的函数
#define itn int
#define fro for
#define ll long long
#define reg register
#define inf 1234567890
/*#include <bitset> //STL位集容器
#include <cstype> //字符处理
#include <cerrno> //定义错误码
#include <complex> //复数类
#include <clocale> //定义本地化函数
#include <cstdlib> //定义杂项函数及内存分配函数
#include <deque> //STL双端队列容器
#include <exception> //异常处理类
#include <fstream> //文件输入/输出
#include <functional> //STL定义运算函数(代替运算符)
#include <limits> //定义各种数据类型最值常量
#include <list> //STL线性列表容器
#include <map> //STL映射容器
#include <iomanip> //参数化输入/输出
#include <ios> //基本输入/输出支持
#include <iosfwd> //输入/输出系统使用的前置声明
#include <istream> //基本输入流
#include <ostream> //基本输出流
#include <queue> //STL队列容器
#include <set> //STL集合容器
#include <sstream> //基于字符串的流
#include <stack> //STL堆栈容器
#include <stdexcept> //标准异常类
#include <streambuf> //底层输入/输出支持
#include <utility> //STL通用模板类
#include <vector> //STL动态数组容器
#include <cwchar.h>//宽字符处理及输入/输出
#include <cwctype.h> //宽字符分类*/

using namespace std;

int ans;

int max(int x,int y){return x>y?x:y;}

int min(int x,int y){return x<y?x:y;}

int read()
{
    int x=0,f=1;char ch=getchar();
    while (ch<'0' || ch>'9'){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

void write(int x)
{
    int buf[50];
    if (x<0) putchar('-'),x=-x;
    buf[0]=0;
    while (x) buf[++buf[0]]=x%10,x/=10;
    if (!buf[0]) buf[0]=1,buf[1]=0;
    while (buf[0]) putchar('0'+buf[buf[0]--]);
}

int fa[300300],ch[300300][3],key[300300],sum[300300],lazy[300300];
int stk[300300],top=0;

int notroot(int x){return ch[fa[x]][0]==x||ch[fa[x]][1]==x;}

void pushr(int x){swap(ch[x][0],ch[x][1]);lazy[x]^=1;}

void pushup(int x){sum[x]=sum[ch[x][0]]^sum[ch[x][1]]^key[x];}

void pushdown(int x)
{
    if (lazy[x])
    {
        if (ch[x][0]) pushr(ch[x][0]);
        if (ch[x][1]) pushr(ch[x][1]);
        lazy[x]=0;
    }
}

void rot(int x)
{
    int y=fa[x],z=fa[y],k=ch[y][1]==x,w=ch[x][!k];
    if (notroot(y)) ch[z][ch[z][1]==y]=x;
    ch[x][!k]=y;ch[y][k]=w;
    if (w) fa[w]=y;fa[y]=x;fa[x]=z;
    pushup(y);
}

void splay(int x)
{
    int y=x,z;top=0;
    stk[++top]=y;
    while (notroot(y)) stk[++top]=y=fa[y];
    while (top) pushdown(stk[top--]);
    while (notroot(x))
    {
        y=fa[x],z=fa[y];
        if (notroot(y))
            rot((ch[y][0]==x)^(ch[z][0]==y)?x:y);
        rot(x);
    }
    pushup(x);
}

void access(int x){for (int y=0;x;x=fa[y=x]) splay(x),ch[x][1]=y,pushup(x);}

void makeroot(int x){access(x);splay(x);pushr(x);}

int findroot(int x)
{
    access(x);splay(x);
    while (ch[x][0]) pushdown(x),x=ch[x][0];
    return x;
}

void split(int x,int y){makeroot(x);access(y);splay(y);}

void link(int x,int y){makeroot(x);if (findroot(y)!=x) fa[x]=y;}

void cut(int x,int y)
{
    makeroot(x);
    if (findroot(y)==x&&fa[x]==y&&!ch[x][1])
        fa[x]=ch[y][0]=0,pushup(y);
}

int main()
{
    int n=read(),m=read();
    for (int i=1;i<=n;i++) key[i]=read();
    while (m--)
    {
        int q=read(),x=read(),y=read();
        if (q==0) {split(x,y);printf("%d\n",sum[y]);}
        if (q==1) link(x,y);
        if (q==2) cut(x,y);
        if (q==3) splay(x),key[x]=y;
    }
    return 0;
}