[cpp]
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=55009;
int n,q,a,b,fa[N],vis[N],ans[N],v[N],Max[N],Min[N],up[N],down[N];
vector<int> need[N],edge[N],kv[N];
int find(int x)
{
if(x==fa[x])return x;
int y=fa[x];
fa[x]=find(fa[x]);
up[x]=max(Max[y]-Min[x],max(up[x],up[y]));
down[x]=max(Max[x]-Min[y],max(down[x],down[y]));
Max[x]=max(Max[y],Max[x]);
Min[x]=min(Min[y],Min[x]);
return fa[x];
}
void tarjan(int x)
{
vis[x]=1;
for(int i=0;i<need[x].size();i=i+2)
{
int y=need[x][i];
if(vis[y])
{
int t=find(y),f=need[x][i+1];
if(f>0)
{
kv[t].push_back(x);
kv[t].push_back(y);
}
else
{
kv[t].push_back(y);
kv[t].push_back(x);
}
kv[t].push_back(f>0?f:-f);
}
}
for(int i=0;i<edge[x].size();i++)
{
int y=edge[x][i];
if(!vis[y])
{
tarjan(y);
fa[y]=x;
}
}
for(int i=0;i<kv[x].size();i=i+3)
{
int a=kv[x][i],b=kv[x][i+1],f=kv[x][i+2];
find(a);find(b);
ans[f]=max(up[a],max(down[b],Max[b]-Min[a]));
}
}
void init()
{
for(int i=0;i<=n;i++)
{
fa[i]=i;
vis[i]=0;
need[i].clear();
edge[i].clear();
kv[i].clear();
}
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
Max[i]=v[i];
Min[i]=v[i];
up[i]=0;
down[i]=0;
}
for(int i=0;i<n-1;i++)
{
scanf("%d%d",&a,&b);
edge[a].push_back(b);
edge[b].push_back(a);
}
scanf("%d",&q);
for(int i=1;i<=q;i++)
{
scanf("%d%d",&a,&b);
need[a].push_back(b);
need[a].push_back(i);
need[b].push_back(a);
need[b].push_back(-i);
}
tarjan(1); www.2cto.com
for(int i=1;i<=q;i++)
{
printf("%d\n",ans[i]);
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
init();
}
}
作者：wsniyufang
