计算过了内存，大概242MB，但是全MLE

#include<bits/stdc++.h>
#include<cmath>
#define ll long long
#define ull unsigned long long
#define ld long double
#define N 100010
#define For(i,a,b) for(ll i=a;i<=b;i++)
#define Rof(i,a,b) for(ll i=a;i>=b;i--)
#define ls x<<1
#define rs x<<1|1
#define lson ls,l,mid
#define rson rs,mid+1,r
#define pb push_back
#define mk make_pair
#define pii pair<ll,ll>
#define pque priority_queue
#define lll __int128

using namespace std;
bool st;
vector<int >e[N];
int a[N];
int n,q;

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int dfn[N],f[N][20],sz[N],top[N],son[N],dep[N],cnt=0;
void dfs1(int u,int fa){
	dep[u]=dep[fa]+1;
	sz[u]=1;
	f[u][0]=fa;
	For(i,1,19) f[u][i]=f[f[u][i-1]][i-1];
	for(int v:e[u]){
		if(v==fa) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
} 
void dfs2(int u,int tp){
	dfn[u]=++cnt;
	top[u]=tp;
	if(son[u]) dfs2(son[u],tp);
	for(int v:e[u]){
		if(v==f[u][0] || v==son[u]) continue;
		dfs2(v,v);
	}
}
int rt[N<<2],to[300*N][2],tot=0;
void add(int now,int x){
	Rof(i,29,0){
		int p=(x>>i)&1;
		if(!to[now][p]) to[now][p]=++tot;
		now=to[now][p];
	}
}
void build(int x,int l,int r,int u,int v){
	add(x,v);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(u<=mid) build(lson,u,v);
	else build(rson,u,v);
}
int qry2(int now,int x){
	int ans=0;
	Rof(i,29,0){
		int p=(x>>i)&1;
		if(to[now][p^1]){
			now=to[now][p^1];
			ans+=(1<<i);
		}else if(to[now][p]) now=to[now][p];
		else break;
	}
	return ans;
}
int qry(int x,int l,int r,int L,int R,int u){
	if(L<=l && r<=R) return qry2(x,u);
	int mid=(l+r)>>1,ans=0;
	if(L<=mid) ans=max(ans,qry(lson,L,R,u));
	if(R>mid) ans=max(ans,qry(rson,L,R,u));
	return ans;
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	Rof(i,19,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	Rof(i,19,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
int sol(int x,int y,int z){
	int ans=0,fu=lca(x,y);
	//cout<<fu<<endl;
	while(top[fu]!=top[x]){
		int now=f[top[x]][0];
		ans=max(ans,qry(1,1,n,dfn[top[x]],dfn[x],z));
		x=now;
	}
	ans=max(ans,qry(1,1,n,dfn[fu],dfn[x],z));
	while(top[fu]!=top[y]){
		int now=f[top[y]][0];
		ans=max(ans,qry(1,1,n,dfn[top[y]],dfn[y],z));
		y=now;
	}
	ans=max(ans,qry(1,1,n,dfn[fu],dfn[y],z));
	return ans;
}
bool ed;

int main()
{
	n=read(),q=read();
	For(i,1,n) a[i]=read();
	For(i,1,n-1){
		int u=read(),v=read();
		e[u].pb(v);
		e[v].pb(u);
	}
	dfs1(1,0);
	dfs2(1,1);
	For(i,1,n*4) rt[i]=i;
	tot=n*4;
	For(i,1,n) build(1,1,n,dfn[i],a[i]);
	//For(i,1,n) cout<<dfn[i]<<' ';
	//cout<<endl;
	while(q--){
		int op=read(),x=read(),y=read(),z;
		if(op==1) printf("%d\n",qry(1,1,n,dfn[x],dfn[x]+sz[x]-1,y));
		else{
			z=read();
			printf("%d\n",sol(x,y,z));
		}
	}
	//fprintf(stderr,"%d\n",(&ed-&st)/1024/1024);
    return 0;
}