本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目描述 Description
水果姐第二天心情也很不错，又来逛水果街。
突然，cgh又出现了。cgh施展了魔法，水果街变成了树结构（店与店之间只有一条唯一的路径）。
同样还是n家水果店，编号为1~n，每家店能买水果也能卖水果，并且同一家店卖与买的价格一样。
cgh给出m个问题，每个问题要求水果姐从第x家店出发到第y家店，途中只能选一家店买一个水果，然后选一家店（可以是同一家店，但不能往回走）卖出去。求最多可以赚多少钱。
水果姐向学过oi的你求助。
输入描述 Input Description
第一行n，表示有n家店
下来n个正整数，表示每家店一个苹果的价格。
下来n-1行，每行两个整数x，y，表示第x家店和第y家店有一条边。
下来一个整数m，表示下来有m个询问。
下来有m行，每行两个整数x和y，表示从第x家店出发到第y家店。
输出描述 Output Description
有m行。
每行对应一个询问，一个整数，表示面对cgh的每次询问，水果姐最多可以赚到多少钱。
样例输入 Sample Input
10
16 5 1 15 15 1 8 9 9 15
1 2
1 3
2 4
2 5
2 6
6 7
4 8
1 9
1 10
6
9 1
5 1
1 7
3 3
1 1
3 6
样例输出
Sample Output
7
11
7
0
0
15
数据范围及提示
Data Size & Hint
0<=苹果的价格<=10^8
0<n<=200000
0<m<=10000
正解：倍增
解题报告：
这道题可以说是一道倍增裸题呢...然而我怎么第一眼就看出是个链剖...
考虑我们的路径是有方向的，也就是说必须是先买后卖。常规思路就是维护往上跳的最大值、最小值和最大收益。但是难以处理往下的情况。
容易发现我们做向上跳的最大收益的时候，是用上面的大-下面的小，那么如果我维护一个新的数组，用下面的大-上面的小就可以得到往下跳的最大收益。同时我维护x到lca的最小值和y到lca的最大值，再用这个最大值减最小值更新一下答案即可。
//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <stack>
using namespace std;
typedef long long LL;
const int MAXN = ;
const int inf = (<<);
int n,m,a[MAXN],deep[MAXN],ecnt,first[MAXN],to[MAXN*],next[MAXN*];
int f[MAXN][],maxl[MAXN][],minl[MAXN][],g[MAXN][],ans,p[MAXN][]; inline int getint(){
int w=,q=; char c=getchar(); while((c<''||c>'') && c!='-') c=getchar();
if(c=='-') q=,c=getchar(); while (c>=''&&c<='') w=w*+c-'',c=getchar(); return q?-w:w;
} inline void dfs(int x,int fa){
for(int i=first[x];i;i=next[i]) {
int v=to[i]; if(v==fa) continue;
f[v][]=x; deep[v]=deep[x]+;
maxl[v][]=max(a[v],a[x]); minl[v][]=min(a[v],a[x]);
g[v][]=max(,a[x]-a[v]);
p[v][]=max(,a[v]-a[x]);
dfs(v,x);
}
} inline void lca(int x,int y){
int t=; int minx=inf,maxy=; ans=;
if(deep[x]<deep[y]) {
while((<<t)<=deep[y]) t++; t--;
for(int i=t;i>=;i--)
if(deep[y]-(<<i)>=deep[x])
ans=max(ans,p[y][i]),ans=max(ans,maxy-minl[y][i]),maxy=max(maxy,maxl[y][i]),y=f[y][i];
}
else{
while((<<t)<=deep[x]) t++; t--;
for(int i=t;i>=;i--)
if(deep[x]-(<<i)>=deep[y])
ans=max(ans,g[x][i]),ans=max(ans,maxl[x][i]-minx),minx=min(minx,minl[x][i]),x=f[x][i];
}
if(x==y) return ;
for(int i=t;i>=;i--) {
if(f[x][i]!=f[y][i]) {
ans=max(g[x][i],ans);
ans=max(p[y][i],ans);
ans=max(ans,maxl[x][i]-minx);
ans=max(ans,maxy-minl[y][i]);
maxy=max(maxy,maxl[y][i]);
minx=min(minx,minl[x][i]);
x=f[x][i]; y=f[y][i];
}
}
ans=max(g[x][],ans);
ans=max(p[y][],ans);
maxy=max(maxy,maxl[y][]);
minx=min(minx,minl[x][]);
ans=max(ans,maxy-minx);
} inline void work(){
n=getint(); for(int i=;i<=n;i++) a[i]=getint(); int x,y;
for(int i=;i<n;i++) {
x=getint(); y=getint();
next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y;
next[++ecnt]=first[y]; first[y]=ecnt; to[ecnt]=x;
}
deep[]=;
dfs(,);
for(int j=;j<=;j++) {
for(int i=;i<=n;i++) {
f[i][j]=f[f[i][j-]][j-];
if(f[i][j]==) continue;
maxl[i][j]=max(maxl[i][j-],maxl[f[i][j-]][j-]);
minl[i][j]=min(minl[i][j-],minl[f[i][j-]][j-]);
g[i][j]=max(g[i][j-],g[f[i][j-]][j-]);
p[i][j]=max(p[i][j-],p[f[i][j-]][j-]);
g[i][j]=max(g[i][j],maxl[f[i][j-]][j-]-minl[i][j-]);
p[i][j]=max(p[i][j],maxl[i][j-]-minl[f[i][j-]][j-]);
}
}
m=getint();
while(m--) {
x=getint(); y=getint();
lca(x,y);
printf("%d\n",ans);
}
} int main()
{
work();
return ;
}