是按区间分块的思路，时间复杂度和高维莫队一样是 $O(n^{\frac{7}{4}})$，但是常数比较大，第11个点就T了。空间复杂度为 $O(n^{\frac{5}{4}})$。设分的块长为 $B$。则具体时间复杂度为 $O(qB+\frac{n^4}{B^3})$，空间复杂度为 $O((\frac{n}{B})^4+\frac{n^2}{B})$，程序里取 $B=n^{\frac{3}{4}}$ 时无法过（理论上此时时最小的），取 $B=6000$ 也无法过。

程序如下

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x){
	x=0;
	register char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[10000];
template<typename item>
inline void print(register item x){
	register long long len=0;
	while(x)cc[len++]=x%10+'0',x/=10;
	while(len--)putchar(cc[len]);
}
const int N=2e5+5;
const int S=39;
int n,q,B,M;
int bel[N],st[S],ed[S];
int a[N],to[N];
struct node{
	int to,nxt;
}e[N<<1];
int head[N],cnt;
inline void add(int u,int v){
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int val[N];
int ldfn[N],rdfn[N];
int dn;
inline void dfs(int u,int fa){
	ldfn[u]=++dn;
	val[dn]=a[u];
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u);
	}
	rdfn[u]=dn;
}
inline void buildtree(){
	read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	for(int i=1;i<n;++i){
		int u,v;
		read(u),read(v);
		add(u,v);
		add(v,u);
	}
	dfs(1,0);
}
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
int vis[S][N];
int pre[S][S][S][S];
int previs[S][S][S][S];
int pre1[S][S];
int previs1[S][S];
int nowt[N],nowvis[N];
inline void initblock(){
	read(q);
	B=6000;
	for(int i=1;i<=n;++i){
		bel[i]=(i-1)/B+1;
		ed[bel[i]]=i;
	}
	for(int i=n;i>=1;--i)
		st[bel[i]]=i;
	M=bel[n];
	int tme=0;
	for(register int l=1;l<=M;++l){
		++tme;
		int now=l;
		int ans=0,mst=0;
		for(register int i=st[l];i<=n;++i){
			if(nowt[val[i]]!=tme) nowt[val[i]]=tme,nowvis[val[i]]=0;
			nowvis[val[i]]++;
			if(nowvis[val[i]]>mst){
				mst=nowvis[val[i]];
				ans=val[i];
			}
			else if(nowvis[val[i]]==mst)
				ans=min(ans,val[i]);
			if(i==ed[now]){
				pre1[l][now]=ans;
				previs1[l][now]=mst;
				++now;
			}
		}
	}
	for(int i=1;i<N;++i) nowt[i]=0,nowvis[i]=0;
	tme=0;
	for(register int l1=1;l1<=M;++l1){
		for(register int r1=l1;r1<=M;++r1){
			for(register int l2=l1;l2<=M;++l2){
				++tme;
				int now=l2;
				int nowmst=previs1[l1][r1],nowmn=pre1[l1][r1];
				for(register int i=st[l2];i<=n;++i){
					if(nowt[val[i]]!=tme) nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					if(nowvis[val[i]]>nowmst){
						nowmst=nowvis[val[i]];
						nowmn=val[i];
					}
					else if(nowvis[val[i]]==nowmst)
						nowmn=min(nowmn,val[i]);
					if(i==ed[now]){
						pre[l1][r1][l2][now]=nowmn;
						previs[l1][r1][l2][now]=nowmst;
						++now;
					}
				}
			}
		}
	}
	for(register int i=1;i<=n;++i)
		vis[bel[i]][val[i]]++;
	for(register int i=2;i<=M;++i){
		for(register int j=1;j<=n;++j)
			vis[i][j]+=vis[i-1][j];
	}
	for(register int i=1;i<N;++i) nowt[i]=0,nowvis[i]=0;
}
inline void solve(){
	for(register int tme=1;tme<=q;++tme){
		int fx,fy;
		read(fx),read(fy);
		int l1=ldfn[fx],r1=rdfn[fx];
		int l2=ldfn[fy],r2=rdfn[fy];
		if(l1>l2){
			swap(l1,l2);
			swap(r1,r2);
		}
		int x1=bel[l1],y1=bel[r1];
		int x2=bel[l2],y2=bel[r2];
		int ans=0,mst=0;
		if(y1-x1<=1){
			if(y2-x2<=1){
				for(register int i=l1;i<=r1;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=l2;i<=r2;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
			}
			else{
				ans=pre1[x2+1][y2-1];
				mst=previs1[x2+1][y2-1];
				for(register int i=l1;i<=r1;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y2-1][val[i]]-vis[x2][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=l2;i<=ed[x2];++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y2-1][val[i]]-vis[x2][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=st[y2];i<=r2;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y2-1][val[i]]-vis[x2][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
			}
		}
		else{
			if(y2-x2<=1){
				ans=pre1[x1+1][y1-1];
				mst=previs1[x1+1][y1-1];
				for(register int i=l2;i<=r2;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y1-1][val[i]]-vis[x1][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=l1;i<=ed[x1];++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y1-1][val[i]]-vis[x1][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=st[y1];i<=r1;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int apptme=nowvis[val[i]]+vis[y1-1][val[i]]-vis[x1][val[i]];
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
			}
			else{
				ans=pre[x1+1][y1-1][x2+1][y2-1];
				mst=previs[x1+1][y1-1][x2+1][y2-1];
				for(register int i=l1;i<=ed[x1];++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int f1=vis[y1-1][val[i]]-vis[x1][val[i]];
					int f2=vis[y2-1][val[i]]-vis[x2][val[i]];
					int apptme=nowvis[val[i]]+f1+f2;
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=st[y1];i<=r1;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int f1=vis[y1-1][val[i]]-vis[x1][val[i]];
					int f2=vis[y2-1][val[i]]-vis[x2][val[i]];
					int apptme=nowvis[val[i]]+f1+f2;
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=l2;i<=ed[x2];++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int f1=vis[y1-1][val[i]]-vis[x1][val[i]];
					int f2=vis[y2-1][val[i]]-vis[x2][val[i]];
					int apptme=nowvis[val[i]]+f1+f2;
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
				for(register int i=st[y2];i<=r2;++i){
					if(nowt[val[i]]!=tme)
						nowt[val[i]]=tme,nowvis[val[i]]=0;
					nowvis[val[i]]++;
					int f1=vis[y1-1][val[i]]-vis[x1][val[i]];
					int f2=vis[y2-1][val[i]]-vis[x2][val[i]];
					int apptme=nowvis[val[i]]+f1+f2;
					if(apptme>mst){
						mst=apptme;
						ans=val[i];
					}
					else if(apptme==mst)
						ans=min(ans,val[i]);
				}
			}
		}
		print(ans);
		putchar('\n');
	}
	fwrite(obuf,p3-obuf,1,stdout);
}
int main(){
	buildtree();
	initblock();
	solve();
	return 0;
}