rt，不会可持久化 01 trie，写的主席树，和 P3293 类似，一位位贪心钦定那个异或的数。

复杂度大抵是 $\mathcal{O}(m\log^2 |V|)$ 的，不知道为何会 TLE。

这个范围应该卡不掉吧。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,L=1,R=1<<30;
int n,m,a[N],f[20][N],lg[N],dfn[N],ed[N],rt1[N],rt2[N],d[N],cnt;
vector<int>g[N];
struct tree{
    int sum[N*30],ls[N*30],rs[N*30],tot;
    tree(){
        memset(sum,0,sizeof sum);
        memset(ls,0,sizeof ls);
        memset(rs,0,sizeof rs);
        tot=0;
    }
    void insert(int&x,int y,int l,int r,int k){
        x=++tot;
        sum[x]=sum[y]+1;
        if(l==r){
            return;
        }
        int mid=(l+r)>>1;
        if(k<=mid){
            rs[x]=rs[y];
            insert(ls[x],ls[y],l,mid,k);
        }else{
            ls[x]=ls[y];
            insert(rs[x],rs[y],mid+1,r,k);
        }
    }
    bool query(int u,int v,int a,int b,int l,int r,int ql,int qr){
        if(ql<=l&&r<=qr){
            return (sum[u]-sum[v]+sum[a]-sum[b])!=0;
        }
        int mid=(l+r)>>1;
        if(ql<=mid){
            if(query(ls[u],ls[v],ls[a],ls[b],l,mid,ql,qr)){
                return 1;
            }
        }
        if(qr>mid){
            if(query(rs[u],rs[v],rs[a],rs[b],mid+1,r,ql,qr)){
                return 1;
            }
        }
        return 0;
    }

}t1,t2;
void dfs(int u,int fa){
    dfn[u]=++cnt;
    t1.insert(rt1[cnt],rt1[cnt-1],L,R,a[u]);
    t2.insert(rt2[u],rt2[fa],L,R,a[u]);
    for(int i=1;i<=lg[d[u]];++i){
        f[i][u]=f[i-1][f[i-1][u]];
    }
    for(int v:g[u]){
        if(v!=fa){
            d[v]=d[u]+1;
            f[0][v]=u;
            dfs(v,u);
        }
    }
    ed[u]=cnt;
}
int lca(int x,int y){
    if(d[x]<d[y]){
        swap(x,y);
    }
    for(;d[x]!=d[y];x=f[lg[d[x]-d[y]]][x]);
    if(x==y){
        return x;
    }
    for(int i=lg[d[x]];~i;--i){
        if(f[i][x]!=f[i][y]){
            x=f[i][x];
            y=f[i][y];
        }
    }
    return f[0][x];
}
signed main(){
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        lg[i]=log2(i);
    }
    for(int i=1,u,v;i<n;++i){
        cin>>u>>v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs(1,0);
    for(int op,x,y,z,ans;m--;){
        cin>>op;
        ans=0;
        if(op&1){
            cin>>x>>z;
            for(int i=30;~i;--i){
                if((z>>i)&1){
                    ans|=(!t1.query(rt1[ed[x]],rt1[dfn[x]-1],0,0,L,R,ans,ans+(1<<i)-1))<<i;
                }else{
                    ans|=t1.query(rt1[ed[x]],rt1[dfn[x]-1],0,0,L,R,ans+(1<<i),ans+(1<<(i+1))-1)<<i;
                }
            }
            cout<<(z^ans)<<'\n';
        }else{
            cin>>x>>y>>z;
            int k=lca(x,y);
            for(int i=30;~i;--i){
                if((z>>i)&1){
                    ans|=(!t2.query(rt2[x],rt2[k],rt2[y],rt2[f[0][k]],L,R,ans,ans+(1<<i)-1))<<i;
                }else{
                    ans|=t2.query(rt2[x],rt2[k],rt2[y],rt2[f[0][k]],L,R,ans+(1<<i),ans+(1<<(i+1))-1)<<i;
                }
            }
            cout<<(z^ans)<<'\n';
        }
    }
    return 0;
}