[Description]
小 T 要经常进行商务旅行,他所在的国家有 N 个城镇,标号为 1,2,3,...,N,这 N 个城镇构
成一棵树。每个城镇可以买入和卖出货物,同一城镇买入和卖出的价格一样,小 T 想从 a
走到 b,在这过程中,在某个城镇买入一个货物,然后在一个城镇卖出,可以是同一城镇买
入和卖出,使得收益最大,注意不能走回头路。
[Input]
第一行一个数 N,第二行 N 个数,第 i 个数表示城镇 i 买入和卖出货物的价格。
接下来 N – 1 行,每行两个数 a,b,表示 a 到 b 之间有一条双向的道路。
接下一行一个数 Q,表示有 Q 个询问,接下来 Q 行,每行两个数 x,y,表示要求小 T 从 x
到 y 的最大收益。
[Output]
对于每个询问,给出一个答案,各占一行。
[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
[Hint]
对于 50%的数据,0 < n <= 1000,0 < m <= 100
对于 100%的数据,0 < n <= 100000,0 < m <= 10000,0 <= 货物的价格 <= 10^8
设 fa[i][j]表示点 i 的第 2^j 个祖先
ma[i][j]表示点 i 到点 fa[i][j]的最大值。
mi[i][j]表示点 i 到点 fa[i][j]的最小值。
up[i][j]表示点 i 到点 fa[i][j]的最大获利。
down[i][j]表示点 fa[i][j]到点 i 的最大获利。
然后我们可以预处理出这四个数组。
即:
ma[x][i]=max(ma[fa[x][i-1]][i-1],ma[x][i-1]);
mi[x][i]=min(mi[fa[x][i-1]][i-1],mi[x][i-1]);
up[x][i]=max(max(up[fa[x][i-1]][i-1],up[x][i-1]),ma[fa[x][i-1]][i-1]-mi[x][i-1]);
down[x][i]=max(max(down[fa[x][i-1]][i-1],down[x][i-1]),ma[x][i-1]-mi[fa[x][i-1]][i-1]);
在走向最近公共祖先的路径上记录一下历史最小值,在远离最近公共祖先的路径上记录一下历史最大值(在途中和最大获利比较)。最后答案再和历史最大值-历史最小值比较一下即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Node
{
int next,to;
}edge[];
int head[],num,ans,dep[],val[],flag,n,Q;
int fa[][],Min[][],Max[][],Up[][],Down[][];
void add(int u,int v)
{
num++;
edge[num].next=head[u];
head[u]=num;
edge[num].to=v;
}
void dfs(int x,int pa)
{int i;
if (dep[x]) return;
dep[x]=dep[pa]+;
for (i=;i<=;i++)
{
fa[x][i]=fa[fa[x][i-]][i-];
Max[x][i]=max(Max[x][i-],Max[fa[x][i-]][i-]);
Min[x][i]=min(Min[x][i-],Min[fa[x][i-]][i-]);
Up[x][i]=max(Up[x][i-],Up[fa[x][i-]][i-]);
Up[x][i]=max(Up[x][i],Max[fa[x][i-]][i-]-Min[x][i-]);
Down[x][i]=max(Down[x][i-],Down[fa[x][i-]][i-]);
Down[x][i]=max(Down[x][i],Max[x][i-]-Min[fa[x][i-]][i-]);
}
for (i=head[x];i;i=edge[i].next)
{
int v=edge[i].to;
if (v!=pa)
{
Max[v][]=max(val[v],val[x]);
Min[v][]=min(val[v],val[x]);
Up[v][]=max(,val[x]-val[v]);
Down[v][]=max(,val[v]-val[x]);
fa[v][]=x;
dfs(v,x);
}
}
}
int LCA(int x,int y)
{
int i;
if (dep[x]<dep[y]) swap(x,y);
for (i=;i>=;i--)
if ((<<i)<=dep[x]-dep[y])
{
x=fa[x][i];
}
if (x==y)
{
//cout<<"LCA:"<<' '<<x<<endl;
return x;
}
for (i=;i>=;i--)
if (fa[x][i]!=fa[y][i])
{
x=fa[x][i];
y=fa[y][i];
}
x=fa[x][];
y=fa[y][];
//cout<<"LCA:"<<' '<<x<<endl;
return x;
}
void get_ans(int x,int y,int lca)
{int i;
int a=,b=,minv=2e9,maxv=;
int small=2e9,large=;
for (i=;i>=;i--)
if ((<<i)<=dep[x]-dep[lca])
{
b=max(b,Up[x][i]);
b=max(b,Max[x][i]-small);
small=min(small,Min[x][i]);
minv=min(minv,Min[x][i]);
x=fa[x][i];
}
for (i=;i>=;i--)
if ((<<i)<=dep[y]-dep[lca])
{
a=max(a,Down[y][i]);
a=max(a,large-Min[y][i]);
large=max(large,Max[y][i]);
maxv=max(maxv,Max[y][i]);
y=fa[y][i];
}
ans=max(a,max(b,maxv-minv));
return;
}
int main()
{int i,u,v,x,y;
freopen("business.in","r",stdin);
freopen("business.out","w",stdout);
cin>>n;
memset(Min,,sizeof(Min));
for (i=;i<=n;i++)
scanf("%d",&val[i]);
for (i=;i<n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
dfs(,);
cin>>Q;
while (Q--)
{
scanf("%d%d",&x,&y);
if (x==y) printf("0\n");
else
{
int lca=LCA(x,y);
get_ans(x,y,lca);
printf("%d\n",ans);
}
}
}