题意
一棵\(n\) 个点的有根树，每个点有点权，\(q\) 次询问，分为两种：
1 x z：查询节点 \(x\) 的子树中的节点权值与 \(z\) 异或结果的最大值。2 x y：查询节点 \(x\) 到节点 \(y\) 的简单路径上的节点的权值与 \(z\) 异或结果最大值。
\(n,q\le10^5\)。
思路
使用可持久化字典树维护。
操作 \(1\)
用版本号表示 \(dfn\) 序，维护一下每个点被经过了几次，查询直接两个版本次数相减，判断是否大于 \(0\)。
操作 \(2\)
用版本号表示点，每个点从祂父亲的版本更新，查询时找一下 \(lca\)，其祂和操作 \(1\) 一样。
代码
// Problem: P4592 [TJOI2018] 异或
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4592
// Memory Limit: 250 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=100010;
int n,q,val[maxn],fa[maxn][30],deep[maxn],dfn[maxn],cnt_dfn,en[maxn],o[maxn];
vector<int>e[maxn];
class Trie{
private:struct node{int ch[2],cnt;}t[maxn*32];int rt[maxn],cnt;
public:void insert(int id,int pre,int val){rt[id]=++cnt;int u=rt[id],uu=rt[pre];for(int i=30;i>=0;i--){int ch=!!(val&(1<<i));t[u].ch[!ch]=t[uu].ch[!ch];t[u].ch[ch]=++cnt;u=t[u].ch[ch],uu=t[uu].ch[ch];t[u].cnt=t[uu].cnt+1;}}int query(int l,int r,int val){int u=rt[r],uu=rt[l],ans=0;for(int i=30;i>=0;i--){int ch=!(val&(1<<i));if(t[t[u].ch[ch]].cnt-t[t[uu].ch[ch]].cnt) u=t[u].ch[ch],uu=t[uu].ch[ch],ans|=(1<<i);else u=t[u].ch[!ch],uu=t[uu].ch[!ch];}return ans;}
}t1,t2;
void dfs(int u){dfn[u]=++cnt_dfn;o[cnt_dfn]=u;t1.insert(u,fa[u][0],val[u]);deep[u]=deep[fa[u][0]]+1;for(int i=1;i<=17;i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(int v:e[u]){if(v==fa[u][0]) continue;fa[v][0]=u;dfs(v);}en[u]=cnt_dfn;
}
int lca(int u,int v){if(deep[u]<deep[v]) swap(u,v);for(int i=17;i>=0;i--) if(deep[fa[u][i]]>=deep[v]) u=fa[u][i];if(u==v) return u;for(int i=17;i>=0;i--) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];return fa[u][0];
}
signed main(){read(n,q);for(int i=1;i<=n;i++) read(val[i]);for(int i=1;i<n;i++){int u,v;read(u,v);e[u].push_back(v),e[v].push_back(u);}dfs(1);for(int i=1;i<=n;i++) t2.insert(i,i-1,val[o[i]]);for(int i=1;i<=q;i++){int op,x,y,z;read(op,x);if(op==1){read(z);write(t2.query(dfn[x]-1,en[x],z));}else{read(y,z);int l=lca(x,y);write(max(t1.query(fa[l][0],x,z),t1.query(fa[l][0],y,z)));}write("\n");}return 0;
}