/*我尼玛 又一个min打成max 看了半天....*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 200010 #define inf 0x7fffffff using namespace std; int n,m,head[maxn],num,v[maxn],fa[maxn][25],c[maxn]; int mii[maxn][25],mxx[maxn][25],up[maxn][25],down[maxn][25]; struct node{ int v,pre; }e[maxn*2]; int init(){ int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Add(int from,int to){ num++;e[num].v=to; e[num].pre=head[from]; head[from]=num; } void Dfs(int now,int from,int dep,int val){ fa[now][0]=from;c[now]=dep; mii[now][0]=min(val,v[now]); mxx[now][0]=max(val,v[now]); up[now][0]=max(0,v[from]-v[now]); down[now][0]=max(0,v[now]-v[from]); for(int i=head[now];i;i=e[i].pre){ if(e[i].v==from)continue; Dfs(e[i].v,now,dep+1,v[now]); } } void Get_fa(){ for(int j=1;j<=20;j++) for(int i=1;i<=n;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; mii[i][j]=min(mii[i][j-1],mii[fa[i][j-1]][j-1]); mxx[i][j]=max(mxx[i][j-1],mxx[fa[i][j-1]][j-1]); up[i][j]=max(up[i][j-1],up[fa[i][j-1]][j-1]); up[i][j]=max(up[i][j],mxx[fa[i][j-1]][j-1]-mii[i][j-1]); down[i][j]=max(down[i][j-1],down[fa[i][j-1]][j-1]); down[i][j]=max(down[i][j],mxx[i][j-1]-mii[fa[i][j-1]][j-1]); } } int LCA(int a,int b){ if(c[a]<c[b])swap(a,b); int t=c[a]-c[b]; for(int i=0;i<=20;i++) if((1<<i)&t)a=fa[a][i]; if(a==b)return a; for(int i=20;i>=0;i--) if(fa[a][i]!=fa[b][i]){ a=fa[a][i]; b=fa[b][i]; } return fa[a][0]; } int Up_lca(int a,int b){ int t=c[a]-c[b],ret=0,minner=inf; for(int i=0;i<=20;i++) if((1<<i)&t){ ret=max(ret,up[a][i]); ret=max(ret,mxx[a][i]-minner); minner=min(minner,mii[a][i]); a=fa[a][i]; } return ret; } int Down_lca(int a,int b){ int t=c[a]-c[b],ret=0,maxxer=0; for(int i=0;i<=20;i++) if((1<<i)&t){ ret=max(ret,down[a][i]); ret=max(ret,maxxer-mii[a][i]); maxxer=max(maxxer,mxx[a][i]); a=fa[a][i]; } return ret; } int Query_max(int a,int b){ int t=c[a]-c[b],maxxer=v[a]; for(int i=0;i<=20;i++) if((1<<i)&t){ maxxer=max(maxxer,mxx[a][i]); a=fa[a][i]; } return maxxer; } int Query_min(int a,int b){ int t=c[a]-c[b],minner=v[a]; for(int i=0;i<=20;i++) if((1<<i)&t){ minner=min(minner,mii[a][i]); a=fa[a][i]; } return minner; } int main() { n=init(); for(int i=1;i<=n;i++) v[i]=init(); int u,v; for(int i=1;i<n;i++){ u=init();v=init(); Add(u,v);Add(v,u); } memset(mii,127,sizeof(mii)); Dfs(1,0,0,0);Get_fa(); m=init(); while(m--){ u=init();v=init(); int anc=LCA(u,v); //printf("%d ",anc); int ans=0; ans=max(Up_lca(u,anc),Down_lca(v,anc)); ans=max(ans,Query_max(v,anc)-Query_min(u,anc)); printf("%d ",ans); } return 0; }