// I may fail a thousand times
// But there is no giving up
// IOI - here I come
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
int a[(int)8e4+5];
int tin[(int)8e4+5];
int tout[(int)8e4+5];
int dist[(int)8e4+5];
int comp[(int)8e4+5];
int par[(int)8e4+5][17];
int mark[(int)8e4+5];
pair<int,int> tree[300][1200][4];
vector<int> g[(int)8e4+5];
vector<pair<int,int>> seg;
int root,root2,mx,timer;
void add_edge(int u,int v){
	g[u].push_back(v);
	g[v].push_back(u);
}
void dfs(int v,int p,int d){
	if(d>mx)root=v;
	for(int u:g[v])if(u!=p)dfs(u,v,d+1);
}
void dfs2(int v,int p,int d=0){
	tin[v]=++timer;
	dist[v]=d;
	par[v][0]=p;
	for(int u:g[v])if(u!=p)dfs2(u,v,d+1);
	tout[v]=++timer;
}
int is_ancestor(int v,int u){
	return (tin[v]<=tin[u]&&tout[v]>=tout[u]);
}
int lca(int u,int v){
	if(is_ancestor(u,v))return u;
	if(is_ancestor(v,u))return v;
	for(int i=17;i>=0;i--){
		if(!is_ancestor(par[u][i],v))
		u=par[u][i];
	}
	return par[u][0];
}
int distance(int u,int v){
	return dist[u]+dist[v]-2*dist[lca(u,v)];
}
void build(int k,int v,int l,int r){
	if(l==r){
		tree[k][v][0]={distance(a[l+seg[k].first-1],root),a[l+seg[k].first-1]};
		tree[k][v][1]=tree[k][v][0];
		tree[k][v][2]={distance(a[l+seg[k].first-1],root2),a[l+seg[k].first-1]};
		tree[k][v][3]=tree[k][v][2];
		return;
	}
	int m=(l+r)/2;
	build(k,2*v,l,m);
	build(k,2*v+1,m+1,r);
	tree[k][v][0]=min(tree[k][2*v][0],tree[k][2*v+1][0]);
	tree[k][v][1]=max(tree[k][2*v][1],tree[k][2*v+1][1]);
	tree[k][v][2]=min(tree[k][2*v][2],tree[k][2*v+1][2]);
	tree[k][v][3]=max(tree[k][2*v][3],tree[k][2*v+1][3]);
}
void build(int k){
	build(k,1,1,seg[k].second-seg[k].first+1);
}
pair<pair<pair<int,int>,pair<int,int>>,pair<pair<int,int>,pair<int,int>>> qry(int k,int v,int l,int r,int ql,int qr){
	if(l>r||l>qr||r<ql)return {{{0,0},{0,0}},{{0,0},{0,0}}};
	if(l==ql&&r==qr){
		return {{tree[k][v][0],tree[k][v][1]},{tree[k][v][2],tree[k][v][3]}};
	}
	int m=(l+r)/2;
	auto lc=qry(k,2*v,l,m,ql,min(m,qr));
	auto rc=qry(k,2*v+1,m+1,r,max(ql,m+1),qr);
	pair<int,int> p1=min(lc.first.first,rc.first.first);
	pair<int,int> p2=max(lc.first.second,rc.first.second);
	pair<int,int> p3=min(lc.second.first,rc.second.first);
	pair<int,int> p4=max(lc.second.second,rc.second.second);
	return {{p1,p2},{p3,p4}};
}
int qry(int k,int l,int r,int x){
	auto res=qry(k,1,1,seg[k].second-seg[k].first+1,l-seg[k].first+1,r-seg[k].first+1);
	int ret=max({distance(res.first.first.second,x),distance(res.first.second.second,x),
							distance(res.second.first.second,x),distance(res.second.second.second,x)});
	return ret;
}
signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1,u,v;i<n;i++)cin>>u>>v,add_edge(u,v);
	root=1,mx=0;dfs(root,root,0);root2=root,mx=0;dfs(root,root,0);
	dfs2(root,root);
	for(int j=1;j<=17;j++){
		for(int i=1;i<=n;i++){
			par[i][j]=par[par[i][j-1]][j-1];
		}
	}
	int sqrtn=500,rem=n%sqrtn;
	for(int i=1;i<=n;i+=sqrtn){
		seg.push_back({i,i});
		for(int j=i;j<=min(n,(rem>0)+i+sqrtn-1);j++)comp[j]=(int)seg.size()-1,seg.back().second=j;
		if(rem)i++,rem--;
		build((int)seg.size()-1);
	}
	int m;cin>>m;
	stack<int> st;
	stack<int> st2;
	for(;m;m--){
		int t;cin>>t;
		if(t==1){
			int u,v;cin>>u>>v;
			swap(a[u],a[v]);
			st.push(comp[u]);
			st.push(comp[v]);
		}else {
			int l,r,x;cin>>l>>r>>x;
			int ans=0;
			for(;!st.empty();){
				if(!mark[st.top()]{
					mark[st.top()]=1
					build(st.top());
					st2.push(st.top());
				}
				st.pop();
			}
			for(;!st2.empty();){
				mark[st2.top()]=0;
				st2.pop();
			}
			for(int i=comp[l];i<=comp[r];i++){
				ans=max(ans,qry(i,max(l,seg[i].first),min(r,seg[i].second),x));
			}
			cout<<ans<<'\n';
		}
	}
  return 0;
}