#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,res,Q,K,u1,u2,vec,man,perm[80005],tin[80005],tout[80005],timer=0,root,dist[80005],stmin[265000],stmax[265000],tip,l,r,x,dfsa[80005],dfspok=1,udaljenost[4005][4005],rod[80005][30];
int del,vred,v1,v2,cp[300][80005],cpvred[80005],cppok;
struct slog{
   int d1,d2,nab;
} mark[80005],mark2[80005];
bool oznacen[80005],sl2=true,sl3=true,sl4=true;
vector<int> stablo[80005];
void nanize(int gde,int pret){
   if(stablo[gde].size()==1){
      mark[gde].d1=0;
      mark[gde].d2=0;
      mark[gde].nab=gde;
      return;
   }
   mark[gde].d1=0;
   mark[gde].d2=0;
   mark[gde].nab=gde;
   //cout<<gde<<endl;
   for(int i=0;i<stablo[gde].size();i++){
      if(stablo[gde][i]==pret)
         continue;
      nanize(stablo[gde][i],gde);
      int d1=mark[stablo[gde][i]].d1;
      int d2=mark[stablo[gde][i]].d2;
     // cout<<stablo[gde][i]<<" "<<d1<<" "<<d2<<endl;
      if(oznacen[stablo[gde][i]] or d1>0){
         d1++;
         d2++;
      }
     // cout<<d1<<" "<<d2<<endl;
      if(d1>mark[gde].d1){
         mark[gde].d2=mark[gde].d1;
         mark[gde].d1=d1;
         mark[gde].nab=stablo[gde][i];
      }
      else if(d1>mark[gde].d2)
         mark[gde].d2=d1;
   }
   return;
}
void nadji(int gde,int pret){
   if(gde==root){
      cp[cppok][gde]=mark[gde].d1;
      mark2[gde].d1=mark[gde].d1;
      mark2[gde].d2=mark[gde].d2;
      mark2[gde].nab=mark[gde].nab;
      for(int i=0;i<stablo[gde].size();i++)
         nadji(stablo[gde][i],gde);
      return;
   }
   vred=mark[gde].d1;
   mark2[gde].d1=mark[gde].d1;
   mark2[gde].d2=mark[gde].d2;
   mark2[gde].nab=mark[gde].nab;
   if(mark2[pret].nab==gde){
      if(mark2[pret].d2+1>=mark2[gde].d1){
         mark2[gde].d2=mark2[gde].d1;
         mark2[gde].d1=mark2[pret].d2+1;
         mark2[gde].nab=pret;
      }
      else if(mark2[pret].d2+1>=mark2[gde].d2)
         mark2[gde].d2=mark2[pret].d2+1;
   }
   else
      if(mark2[pret].d1+1>=mark2[gde].d1){
         mark2[gde].d2=mark2[gde].d1;
         mark2[gde].d1=mark2[pret].d1+1;
         mark2[gde].nab=pret;
      }
      else if(mark2[pret].d1+1>=mark2[gde].d2)
         mark2[gde].d2=mark2[pret].d1+1;
   cp[cppok][gde]=mark2[gde].d1;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         nadji(stablo[gde][i],gde);
   return;
}
void dfs2(int gde,int dub){
   dfsa[gde]=dfspok;
   dist[gde]=dub;
   for(int i=0;i<stablo[gde].size();i++)
      if(dfsa[stablo[gde][i]]<dfspok)
         dfs2(stablo[gde][i],dub+1);
   return;
}
void dfs4(int gde,int pret){
   tin[gde]=++timer;
   rod[gde][0]=pret;
   for(int i=0;i<stablo[gde].size();i++)
      if(stablo[gde][i]!=pret)
         dfs4(stablo[gde][i],gde);
   tout[gde]=++timer;
   return;
}
bool predak(int u,int v){
   return tin[u]<=tin[v] and tout[u]>=tout[v];
}
int LCA(int u,int v){
   if(predak(u,v))
      return u;
   if(predak(v,u))
      return v;
   for(int i=19;i>=0;i--)
      if(!predak(rod[u][i],v))
         u=rod[u][i];
   return rod[u][0];
}
int dopretka(int u,int pred){
   if(u==pred)
      return 0;
   int step=1<<19,ret=0;
   for(int i=19;i>=0;i--){
      if(!predak(rod[u][i],pred)){
         ret+=step;
         u=rod[u][i];
      }
      step/=2;
   }
   return ret+1;
}
int razdaljina(int u,int v){
   int lca=LCA(u,v);
   return dopretka(u,lca)+dopretka(v,lca);
}
void update2(int gde){
   gde/=2;
   while(gde>=1){
      stmax[gde]=max(stmax[gde*2],stmax[gde*2+1]);
      stmin[gde]=min(stmin[gde*2],stmin[gde*2+1]);
      gde/=2;
   }
   return;
}
ll getmax(int gde,int lg,int dg,int lc,int dc){
   if(lg==lc and dg==dc)
      return stmax[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmax(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmax(gde*2+1,lg,dg,sred+1,dc);
   ll v1,v2;
   v1=getmax(gde*2,lg,sred,lc,sred);
   v2=getmax(gde*2+1,sred+1,dg,sred+1,dc);
   return max(v1,v2);
}
ll getmin(int gde,int lg,int dg,int lc,int dc){
   if(lg==lc and dg==dc)
      return stmin[gde];
   int sred=(lc+dc)/2;
   if(dg<=sred)
      return getmin(gde*2,lg,dg,lc,sred);
   if(lg>sred)
      return getmin(gde*2+1,lg,dg,sred+1,dc);
   ll v1,v2;
   v1=getmin(gde*2,lg,sred,lc,sred);
   v2=getmin(gde*2+1,sred+1,dg,sred+1,dc);
   return min(v1,v2);
}
void dfs1(int gde,int dub){
   dfsa[gde]=dfspok;
   udaljenost[dfspok][gde]=dub;
   for(int i=0;i<stablo[gde].size();i++)
      if(dfsa[stablo[gde][i]]<dfspok)
         dfs1(stablo[gde][i],dub+1);
   return;
}
struct query{
   int tip,l,r,x;
}qniz[80005];
int main(){
   freopen("Input.txt","r",stdin);
   freopen("Output1.txt","w",stdout);
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   cin>>N;
   for(int i=1;i<=N;i++)
      cin>>perm[i];
   for(int i=1;i<N;i++){
      cin>>u1>>u2;
      stablo[u1].push_back(u2);
      stablo[u2].push_back(u1);
      if(stablo[u1].size()>2 or stablo[u2].size()>2)
         sl2=false;
   }
   cin>>Q;
   if(N<=4000 and Q<=4000){
      for(dfspok=1;dfspok<=N;dfspok++)
         dfs1(dfspok,0);
      while(Q--){
         cin>>tip;
         if(tip==1){
            cin>>l>>r;
            swap(perm[l],perm[r]);
            continue;
         }
         res=0;
         cin>>l>>r>>x;
         for(int i=l;i<=r;i++)
            res=max(res,udaljenost[x][perm[i]]);
         cout<<res<<endl;
      }
      return 0;
   }
   if(sl2){
      for(int i=1;i<=N;i++)
         if(stablo[i].size()==1){
            root=i;
            break;
         }
      memset(stmin,1e9,sizeof(stmin));
      dfs2(root,0);
      K=1;
      while(K<N)
         K*=2;
      for(int i=1;i<=N;i++)
         stmax[K+i-1]=stmin[K+i-1]=dist[perm[i]];
      for(int i=K-1;i>=1;i--){
         stmax[i]=max(stmax[i*2],stmax[i*2+1]);
         stmin[i]=min(stmin[i*2],stmin[i*2+1]);
      }
      while(Q--){
         cin>>tip;
         if(tip==1){
            cin>>l>>r;
            swap(stmin[perm[l]+K-1],stmin[perm[r]+K-1]);
            //cout<<stmin[perm[l]+K-1]<<" "<<stmin[perm[r]+K-1]<<endl;
            swap(stmax[perm[l]+K-1],stmax[perm[r]+K-1]);
            //cout<<stmax[perm[l]+K-1]<<" "<<stmax[perm[r]+K-1]<<endl;
            update2(perm[l]+K-1);
            update2(perm[r]+K-1);
            continue;
         }
         cin>>l>>r>>x;
         vec=getmax(1,l,r,1,K);
         man=getmin(1,l,r,1,K);
       //  cout<<man<<" "<<vec<<endl;
         cout<<max(abs(dist[x]-vec),abs(dist[x]-man))<<endl;
      }
      return 0;
   }
   for(int i=1;i<=Q;i++){
      cin>>qniz[i].tip>>qniz[i].l>>qniz[i].r;
      if(qniz[i].tip==2){
         cin>>qniz[i].x;
         if(qniz[i].x!=1)
            sl3=false;
      }
      if(qniz[i].tip==1){
         sl4=false;
      }
   }
   if(sl3){
      dfs2(1,0);
      K=1;
      while(K<N)
         K*=2;
      //cout<<"K "<<K<<endl;
      for(int i=1;i<=N;i++)
         stmax[K+i-1]=dist[perm[i]];
      for(int i=K-1;i>=1;i--)
         stmax[i]=max(stmax[i*2],stmax[i*2+1]);
      /*for(int i=1;i<=2*K-1;i++)
            cout<<stmax[i]<<" ";
         cout<<endl;*/
      for(int i=1;i<=Q;i++){
         if(qniz[i].tip==1){
            swap(perm[qniz[i].l],perm[qniz[i].r]);
          //  cout<<"PERM"<<endl;
          //  cout<<perm[qniz[i].l]<<" "<<perm[qniz[i].r]<<endl;
           // cout<<dist[perm[qniz[i].l]]<<" "<<dist[perm[qniz[i].r]]<<endl;
            stmax[qniz[i].l+K-1]=dist[perm[qniz[i].l]];
            stmax[qniz[i].r+K-1]=dist[perm[qniz[i].r]];
            update2(qniz[i].l+K-1);
            update2(qniz[i].r+K-1);
           /* for(int i=1;i<=2*K-1;i++)
               cout<<stmax[i]<<" ";
            cout<<endl;*/
            continue;
         }
         cout<<getmax(1,qniz[i].l,qniz[i].r,1,K)<<endl;
      }
      return 0;
   }
   if(sl4){
      for(int i=1;i<=N;i++)
         if(stablo[i].size()!=0){
            root=i;
            break;
         }
      memset(rod,root,sizeof(rod));
      dfs4(root,root);
      for(int j=1;j<=20;j++)
         for(int i=1;i<=N;i++)
            rod[i][j]=rod[rod[i][j-1]][j-1];
      del=round(sqrt((double)N));
     // cout<<del<<endl;
      cppok=1;
      for(int i=1;i+del-1<=N;i+=del){
         for(int j=i;j<=i+del-1;j++)
            oznacen[perm[j]]=true;
         nanize(root,root);
      //   for(int i=1;i<=N;i++)
      //      cout<<i<<": "<<mark[i].d1<<" "<<mark[i].d2<<" "<<mark[i].nab<<endl;
         nadji(root,root);
         cpvred[i]=cppok;
         cppok++;
      /*   cout<<"OZNACENI"<<endl;
         for(int j=i;j<=i+del-1;j++)
            cout<<j<<" ";
         cout<<endl;
         for(int i=1;i<=N;i++)
            cout<<cp[cppok-1][i]<<" ";
         cout<<endl;*/
         for(int j=i;j<=i+del-1;j++)
            oznacen[perm[j]]=false;
      }
      for(int j=1;j<=Q;j++){
         l=qniz[j].l;
         r=qniz[j].r;
         x=qniz[j].x;
         res=0;
         for(int i=l;i<=r;i++){
            if(cpvred[i]!=0 and i+del-1<=r){
               res=max(res,(ll)cp[cpvred[i]][x]);
               i+=del-1;
            }
            else
               res=max(res,(ll)razdaljina(x,perm[i]));
         }
         cout<<res<<endl;
      }
      return 0;
   }
}