题意：有n个城市，有n-1条边使各个城市相互直接或间接连通，给出一件货物在各城市的价格w[n]，然后给出q个询问，每个询问有两个城市s,t，问从s到t的路径上买入卖出货物盈利的最大值。注意：在某个城市买入，只能够在其后经过的城市卖出。

分析：假设询问从城市u到城市v的路径上所能获得的最大盈利值，又设lca为u,v的LCA，则u->v的路径就是u->lca->v，那么最大的盈利值就有可能出现在3种情况：
1.在u->lca中出现；
2.在lca->v中出现；
3.在u->lca->v中出现（即有跨过lca）。
第3种情况是比较容易解决的，我们只要求出lca->v中的最大值max_val，减去u->lca中的最小值min_val，max_val-min_val就是答案，因此对于这种情况我们可以设置ma[i][j]，mi[i][j]分别表示：
ma[i][j]：在i结点往上跳2^j步到达的结点的路径当中的最大价格；
mi[i][j]：在i结点往上跳2^j步到达的结点的路径当中的最小价格。
对于第1,2种情况，我们同样可以考虑分治。以第1种情况为例，设k为u->lca路径当中某个结点，那么u->lca可分解为u->k，k->lca。那么最终答案就同样会有3种情况：
1 .在u->k中出现；
2 .在k->lca中出现；
3 .在u->lca中出现（即跨过结点k）。
仿照第3种情况，我们同样可以用倍增的思想来解决。设置up[i][j]表示：
up[i][j]：在i结点往上跳2^j步到达的结点的路径当中，最大的价格差（当然，最大价格出现的位置一定要在最小价格出现的位置之后）。
根据上述分析，不难推出up[i][j]的更新方式：
up[i][j]=max(max(up[i][j-1],up[k][j-1]), ma[k][j]-mi[i][j])
其中k=fa[i][j-1]，即在i结点往上跳2^j-1步到达的结点。
第2种情况与第3种情况相似，可以设置down[i][j]表示：
down[i][j]：设k为在i结点往上跳2^j步到达的结点，down[i][j]为k->i的路径当中，最大的价格差。

代码如下：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int inf=0x3f3f3f3f;
int depth[maxn],fa[maxn][20];
ll ma[maxn][20],mi[maxn][20];
ll up[maxn][20],down[maxn][20];
ll w[maxn];
bool vis[maxn];
vector<int> G[maxn];

inline void read(ll &ret)
{
	char c;
	while((c=getchar())&&(c>'9'||c<'0'));
	ret=0;
	while(c>='0'&&c<='9')	ret=ret*10+c-'0', c=getchar();
}

inline void out(ll x)
{
	if(x>9)	out(x/10);
	putchar(x%10+'0');
}

void DFS(int u,int pre,int d)
{
	fa[u][0]=pre;	ma[u][0]=max(w[u],w[pre]);	
	up[u][0]=max(0ll,w[pre]-w[u]);	
	vis[u]=1;	depth[u]=d;
	if(u!=1)	mi[u][0]=min(w[u],w[pre]), down[u][0]=max(0ll,w[u]-w[pre]);
	else mi[u][0]=w[u],	down[u][0]=0;
	for(int i=0;i<G[u].size();++i)
	{
		if(!vis[G[u][i]])
		{
			DFS(G[u][i],u,d+1);
		}
	}
}

void init(int n)
{
	for(int i=1;i<=n;++i)	vis[i]=0;
	w[0]=0;
	DFS(1,0,1);
	for(int j=1;(1<<j)<n;++j)
		for(int i=1;i<=n;++i)
		{
			if(!fa[i][j-1])
			{
				fa[i][j]=fa[i][j-1];	ma[i][j]=ma[i][j-1];	
				mi[i][j]=mi[i][j-1];	up[i][j]=up[i][j-1];
				down[i][j]=down[i][j-1];
			}
			else
			{
				fa[i][j]=fa[fa[i][j-1]][j-1];
				ma[i][j]=max(ma[i][j-1],ma[fa[i][j-1]][j-1]);
				mi[i][j]=min(mi[i][j-1],mi[fa[i][j-1]][j-1]);
				up[i][j]=max(max(up[i][j-1],up[fa[i][j-1]][j-1]),ma[fa[i][j-1]][j-1]-mi[i][j-1]);
				down[i][j]=max(max(down[i][j-1],down[fa[i][j-1]][j-1]),ma[i][j-1]-mi[fa[i][j-1]][j-1]);
			}
		}
}

ll go_up(int deep,int x,ll &min_val)	//min_val记录u->lca中的最小值，同时也会发挥其他作用
{
	ll ans=0;
	for(int i=20;i>=0;--i)
	{
		if((1<<i)&deep)
		{
			ans = max(ans,up[x][i]);
			ans = max(ans,ma[x][i] - min_val);	//有点难讲，自行理解
			min_val = min(min_val,mi[x][i]);
			x=fa[x][i];
		}
	}
	return ans;
}

ll go_down(int deep,int x,ll &max_val)	//max_val记录lca->v中的最大值，同样也会发挥其他作用
{
	ll ans=0;
	for(int i=20;i>=0;--i)
	{
		if((1<<i)&deep)
		{
			ans = max(ans,down[x][i]);
			ans = max(ans,max_val-mi[x][i]);	//自行理解
			max_val = max(max_val,ma[x][i]);
			x=fa[x][i];
		}
	}
	return ans;
}

int LCA(int u,int v,int n)
{
	if(depth[v]>depth[u])	swap(u,v);
	int temp=depth[u]-depth[v];
	for(int i=0;(1<<i)<=temp;++i)
	{
		if((1<<i)&temp)
			u=fa[u][i];
	}
	if(u==v)	return u;
	int k=0;
	while((1<<(k+1))<=n)	++k;
	for(int i=k;i>=0;--i)
	{
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];	
			v=fa[v][i];
		}
	}
	return fa[u][0];
}

int main()
{
	ll n;
	read(n);
	for(int i=1;i<=n;++i)	read(w[i]);
	for(int i=1;i<n;++i)
	{
		ll u,v;
		read(u);	read(v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	init(n);
	ll q;
	read(q);
	while(q--)
	{
		ll u,v;
		read(u);	read(v);
		ll ans,ma1,mi1;
		int lca=LCA(u,v,n);
		ma1=0;	mi1=inf;
		ans=max(0ll,max(go_up(depth[u]-depth[lca],u,mi1),go_down(depth[v]-depth[lca],v,ma1)));
		ans=max(ans,ma1-mi1);
		out(ans);	putchar('\n');
	}
	return 0;
}

PS：分治思想有时可以发挥很大的作用。