模板

给定 n 个点，编号从 1 到 n，其中第 i 个点的初始权值为 ai。

现在要对这些点进行 m 次操作，操作共分为以下 4 种：

0 x y，表示询问点 x 到点 y 之间的路径上的所有点（包括两端点）的权值的异或和。保证 x 和 y 之间存在连通路径。
1 x y，表示在点 x 和点 y 之间增加一条边 (x,y)。注意：如果两点已经处于连通状态，则无视该操作。
2 x y，表示删除边 (x,y)。注意：如果该边不存在，则无视该操作。
3 x w，表示将点 x 的权值修改为 w

#include<bits/stdc++.h>
using namespace std;
const int N =  1e5+9;
struct node
{
    int p,s[2];
    int rev;
    int v,sum,sz;
}tr[N];

int stk[N];


bool isroot(int x)
{
    int fa= tr[x].p;
    return tr[fa].s[1]!=x && tr[fa].s[0]!=x;
}

void push_rev(int x)
{
    swap(tr[x].s[1],tr[x].s[0]);
    tr[x].rev^=1;
}

void up(int x)
{
    tr[x].sum=tr[tr[x].s[1]].sum^tr[x].v^tr[tr[x].s[0]].sum;
}

void down(int x)
{
    if(tr[x].rev)
    {
        push_rev(tr[x].s[1]);
        push_rev(tr[x].s[0]);
        tr[x].rev = 0;
    }
}


void spin(int x)
{
    int y= tr[x].p;
    int z= tr[y].p;
    int k= tr[y].s[1]==x;
    if(!isroot(y))tr[z].s[tr[z].s[1]==y]=x;
    tr[x].p=z;
    tr[y].s[k]=tr[x].s[k^1]; tr[tr[x].s[k^1]].p=y;
    tr[x].s[k^1]=y; tr[y].p=x;
    up(y); up(x);
}

void splay (int x)
{
    int top = 0;
    int r  = x;
    stk[++top]=x;
    while (!isroot(r))stk[++top]=r=tr[r].p;
    while (top) down(stk[top--]);

    while (!isroot(x))
    {
        int y= tr[x].p;
        int z= tr[y].p;

        if(!isroot(y))
        {
            if((tr[y].s[1]==x) ^ (tr[z].s[1]==y))spin(x);
            else spin(y);
        }
        spin(x);
    }
}

void access(int x)
{
    int z =x;
    for (int y= 0; x; y=x,x=tr[x].p)
    {
        splay(x);
        tr[x].s[1]=y;
        up(x);  ///改接树上结构需要up
    }
    splay(z); ///access自带把x转上辅助树的树根
}


int find_root(int x)/// 辅助树的root
{
    access(x);
    while (tr[x].s[0])
    {
        down(x); ///忘记2
        x=tr[x].s[0];
    }
    splay(x);
    return x;
}

void make_root(int x)/// 把x做成原树的根节点，需要反转整个中序遍历
{
    access(x);
    push_rev(x);///q1
}

void sign(int x,int y) ///把x到y的路径标记为实边
{
    make_root(x);
    access(y);
}

void link(int x,int y)
{
    make_root(x);
    if(find_root(y)!=x )tr[x].p=y;
}

void cut(int x,int y)
{
    make_root(x);
    if(find_root(y)==x && tr[y].p==x && !tr[y].s[0])
    {
        tr[x].s[1]=tr[y].p=0;
        up(x);
    }
}



int main()
{
    int n,m;
    cin>>n>>m;
    for (int i =1 ;i<=n;i++)cin>>tr[i].v;
    while (m--)
    {
        int k;
        int a,b;
        cin>>k;
        cin>>a>>b;
        if(k==0)
        {
            sign(a,b);
            cout<<tr[b].sum<<endl;
        }
        if(k==1)link(a,b);
        if(k==2)cut(a,b);
        if(k==3)
        {
            splay(a);
            tr[a].v= b;
            up(a);
        }
    }

    return 0;
}