30pts 求调

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+1;
int n, m, op, x, y;
struct LCT{
    int fa[N], ch[N][2], val[N], sum[N];
    bool rev[N];
    inline bool get(int x){return ch[fa[x]][1] == x;}
    inline bool isroot(int x){return ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
    inline void pushup(int x){sum[x] = sum[ch[x][0]] ^ sum[ch[x][1]] ^ val[x];}
    inline void pushrev(int x){
        if (!x) return;
        swap(ch[x][0], ch[x][1]);
        rev[x] ^= 1;
    }
    inline void pushdown(int x){
        if (rev[x]){
            pushrev(ch[x][0]);
            pushrev(ch[x][1]);
            rev[x] = 0;
        }
    }
    inline void rotate(int x){
        int y = fa[x], z = fa[y];
        bool k = get(x);
        if (!isroot(y)) ch[z][get(y)] = x;
        fa[x] = z;
        if (ch[y][k] = ch[x][!k]) fa[ch[y][k]] = y; // 等价于：ch[y][k] = ch[x][!k]; if (ch[x][!k]) fa[ch[x][!k]] = y;
        ch[x][!k] = y;
        fa[y] = x;
        pushup(y);
        pushup(x);
    }
    inline void splay(int x){
        static int st[N];
        int top = 1, y = x;
        st[1] = y;
        while(!isroot(y)){
            y = fa[y];
            st[++top] = y;
        }
        while(top) pushdown(st[top--]);
        while(!isroot(x)){
            int y = fa[x];
            if (!isroot(y)) rotate(get(x)^get(y) ? x : y);
            rotate(x);
        }
    }
    inline int access(int x){
        int p = 0;
        while(x){
            splay(x);
            ch[x][1] = p;
            p = x;
            x = fa[x];
        }
        return p;
    }
    inline void makeroot(int x){
        access(x);
        splay(x);
        pushrev(x);
    }
    inline int find(int x){
        pushdown(x = access(x));
        while(ch[x][0]) pushdown(x = ch[x][0]);
        splay(x);
        return x;
    }
    inline void split(int x, int y){
        makeroot(x);
        access(y);
        splay(y);
    }
    inline bool link(int x, int y){
        makeroot(x);
        if (find(y) == x) return false;
        splay(x);
        fa[x] = y;
        return true;
    }
    inline bool cut(int x, int y){
        makeroot(x);
        access(y);
        splay(y);
        if(ch[y][0] != x || ch[x][1]) return false;
        ch[y][0] = fa[x] = 0;
        pushup(y);
        return true;
    }
} T;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;++i) cin>>T.val[i];
    while(m--){
        cin>>op>>x>>y;
        if (op==0){
            if (x==y){
                cout << T.val[x] << '\n';
                continue;
            }
            T.split(x, y);
            cout << T.sum[y] << '\n';
        } else if (op==1) T.link(x, y);
        else if (op==2) T.cut(x, y);
        else{
            T.makeroot(x);
            T.val[x] = y;
            T.pushup(x);
        }
    }
}