1 #include<iostream> 2 #include<vector> 3 #include<cstdio> 4 #define F ast[x][i-1] 5 using namespace std; 6 const int N=200010; 7 //Constants;// 8 int n,m,val[N]; 9 vector<int> gr[N];10 //INput;//11 int ans,ast[N][18],depth[N],mxv[N][18],mnv[N][18],up[N][18],dn[N][18];12 bool vis[N];13 //Usage;//14 15 void dfs(int x){16     vis[x]=true;17     for(int i=1;i<=18;i++){18         if(depth[x]<(1<<i))break;19         ast[x][i]=ast[F][i-1];20         21         mxv[x][i]=max(mxv[x][i-1],mxv[F][i-1]);22         mnv[x][i]=min(mnv[x][i-1],mnv[F][i-1]);23         24         up[x][i]=max(max(up[x][i-1],up[F][i-1]),mxv[F][i-1]-mnv[x][i-1]);25         dn[x][i]=max(max(dn[x][i-1],dn[F][i-1]),mxv[x][i-1]-mnv[F][i-1]);26     }27     28     for(int i=0;i<gr[x].size();i++)29         if(!vis[gr[x][i]]){30             int v=gr[x][i];31             ast[v][0]=x;32             depth[v]=depth[x]+1;33             34             mxv[v][0]=max(val[v],val[x]);35             mnv[v][0]=min(val[v],val[x]);36             37             up[v][0]=val[x]-val[v];38             dn[v][0]=val[v]-val[x];39             40             dfs(v);41         }42 }43 44 int lca(int x,int y){45     if(depth[x]<depth[y])swap(x,y);46     int k=depth[x]-depth[y];47     for(int i=0;i<=18;i++)48         if(k&(1<<i))49             x=ast[x][i];50     51     for(int i=18;i>=0;i--)52         if(ast[x][i]!=ast[y][i])53             x=ast[x][i],y=ast[y][i];54     55     if(x==y)return x;56     return ast[x][0];57 }58 59 int calculate(int x,int y){60     int maxn=0,minn=0x7fffffff,pnt=lca(x,y),k;61     ans=0;62     k=depth[x]-depth[pnt];63     if(k>0){64         for(int i=0;i<=18;i++)65             if(k&(1<<i)){66                 ans=max(ans,max(mxv[x][i]-minn,up[x][i]));67                 minn=min(minn,mnv[x][i]);68                 x=ast[x][i];69             }70     }71     k=depth[y]-depth[pnt];72     if(k>0){73         for(int i=0;i<=18;i++)74             if(k&(1<<i)){75                 ans=max(ans,max(maxn-mnv[y][i],dn[y][i]));76                 maxn=max(maxn,mxv[y][i]);77                 y=ast[y][i];78             }79     }80     ans=max(ans,maxn-minn);81 }82 //Function(s);//83 int main(){84     cin>>n;85     for(int i=1;i<=n;i++)cin>>val[i];86     for(int i=1;i<n;i++){87         int x,y;cin>>x>>y;88         gr[x].push_back(y);gr[y].push_back(x);89     }90     ast[1][0]=1;91     dfs(1);92     cin>>m;93     while(m--){94         int x,y;cin>>x>>y;95         calculate(x,y);96         cout<<ans<<endl;97     }98     return 0;99 }