P10799 8pts

#include<algorithm>
#include<iostream>
#include<string.h>
#include<cstdio>
#include<vector>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
#define int long long
#define lb(a,b,n) (lower_bound((a)+1,(a)+1+(n),(b))-(a))
#define repu(i,u) for(int i=(h[u]);i;i=(ne[i]))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dwn(i,a,b) for(int i=(a);i>=(b);i--)
#define debug cout<<"wwww"<<endl
#define llinf 1e18
#define inf 0x3f3f3f3f
#define pb(a) push_back((a))
#define xx return
const int N=2e5+10;

int n,q;
int h[N],e[N*2],ne[N*2],idx;
int wt[N],a[N];
namespace xx_Seg{
	#define ls (p<<1)
	#define rs (p<<1|1)
	#define mid (l+r>>1)
	struct Tree{
		int val,tag;
		#define val(p) t[p].val
		#define tag(p) t[p].tag
	}t[N*4];
	void push_down(int p){
			val(ls)^=tag(p),val(rs)^=tag(p);
			tag(ls)^=tag(p),tag(rs)^=tag(p);
			tag(p)=0;
	}
	void build(int p,int l,int r){
		if(l==r){val(p)=a[wt[l]];xx;}
		build(ls,l,mid),build(rs,mid+1,r);
	}
	void change(int p,int l,int r,int L,int R,int k){
		if(L<=l&&r<=R){val(p)^=k,tag(p)^=k;xx;}push_down(p);
		if(L<=mid)change(ls,l,mid,L,R,k);
		if(R>mid) change(rs,mid+1,r,L,R,k);
	}
	int ask(int p,int l,int r,int x){
		if(l==r)xx val(p);push_down(p);
		if(x<=mid)xx ask(ls,l,mid,x);
		else xx ask(rs,mid+1,r,x);
	}
}

namespace xx_CTT{
	int d[N],fa[N],sizt[N],son[N];
	int top[N],id[N],cnt;
	void dfs1(int u,int fath){
		d[u]=d[fath]+1;fa[u]=fath;sizt[u]=1;
		int max_son=-1;
		repu(i,u){
			int v=e[i];
			if(v==fath)continue;
			dfs1(v,u);
			sizt[u]+=sizt[v];
			if(sizt[v]>max_son)son[u]=v,max_son=sizt[v];
		}
	}
	void dfs2(int u,int topf){
		id[u]=++cnt;wt[cnt]=u;top[u]=topf;
		if(!son[u])xx;dfs2(son[u],topf);
		repu(i,u){
			int v=e[i];
			if(v==fa[u]||v==son[u])continue;
			dfs2(v,v);
		}
	}
	void change(int u,int v,int k){
		while(top[u]!=top[v]){
			if(d[top[u]]<d[top[v]])swap(u,v);
			xx_Seg::change(1,1,n,id[top[u]],id[u],k);
			u=fa[top[u]];
		}
		if(d[u]>d[v])swap(u,v);
		xx_Seg::change(1,1,n,id[u],id[v],k);
		xx;
	}
	int ask1(int u,int v){
		int now=0;
		while(top[u]!=top[v]){
			if(d[top[u]]<d[top[v]])swap(u,v);
			now+=id[u]-id[top[u]]+1;
			u=fa[top[u]];
		}
		if(d[u]>d[v])swap(u,v);
		now+=id[v]-id[u]+1;
		xx now;
	} 
	int ask2(int u,int v){
		vector<int>num;
		while(top[u]!=top[v]){
			if(d[top[u]]<d[top[v]])swap(u,v);
			rep(i,id[top[u]],id[u])num.pb(xx_Seg::ask(1,1,n,i));
			u=fa[top[u]];
		}
		if(d[u]>d[v])swap(u,v);
		rep(i,id[u],id[v])num.pb(xx_Seg::ask(1,1,n,i));
		sort(num.begin(),num.end());
		if(num.size()<3)xx 0;
		rep(i,2,num.size()-1){
			if(num[i-1]>num[i]-num[i-2])xx 1;
		}
		xx 0;
	}
}

namespace Main_xx{
	void add(int a,int b){e[++idx]=b,ne[idx]=h[a],h[a]=idx;}
	void Main(){
		cin>>n>>q;
		rep(i,1,n)cin>>a[i];
		rep(i,1,n-1){
			int u,v;cin>>u>>v;add(u,v),add(v,u);
		}
		xx_CTT::dfs1(1,0);xx_CTT::dfs2(1,1);
		xx_Seg::build(1,1,n);
		while(q--){
			int opt,u,v;cin>>opt>>u>>v;
			if(opt==1){
				int k;cin>>k;
				xx_CTT::change(u,v,k);
			}
			else{
				int ANS=xx_CTT::ask1(u,v);
				if(ANS>=46)cout<<1;
				if(ANS<3)cout<<0;
				if(ANS>=3&&ANS<46){
					if(xx_CTT::ask2(u,v))cout<<1;
					else cout<<0;
				}
			}
		}
		xx;
	}
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	Main_xx::Main();
	xx 0;
}