题目链接:题目
题意:在一个树上,选取两个点,是他们的差值最大,不过较大值应该在较小值路径的前面。
解题思路:倍增lca,然后采用倍增维护信息,第一次学倍增dp。
代码:
/* ***********************************************
Author :xianxingwuguan
Created Time :2014/1/16 20:42:49
File Name :C.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int maxn=60050;
const int inf=100010000;
const int DEG=20;
int head[maxn],tol,mx[maxn][DEG],mi[maxn][DEG],dp[maxn][DEG],dp2[maxn][DEG],fa[maxn][DEG],dep[maxn];
int weight[maxn];
struct node
{
int next,to;
}edge[3*maxn];
void add(int u,int v)
{
edge[tol].to=v;
edge[tol].next=head[u];
head[u]=tol++;
}
int n;
void dfs(int u,int pre)
{
dep[u]=dep[pre]+1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(v==pre)continue;
fa[v][0]=u;
mx[v][0]=max(weight[u],weight[v]);
mi[v][0]=min(weight[u],weight[v]);
dp[v][0]=weight[u]-weight[v];
dp2[v][0]=weight[v]-weight[u];
for(int j=1;j<20;j++)
{
fa[v][j]=fa[fa[v][j-1]][j-1];
mx[v][j]=max(mx[v][j-1],mx[fa[v][j-1]][j-1]);
mi[v][j]=min(mi[v][j-1],mi[fa[v][j-1]][j-1]);
dp[v][j]=max(dp[v][j-1],dp[fa[v][j-1]][j-1]);
dp[v][j]=max(dp[v][j],mx[fa[v][j-1]][j-1]-mi[v][j-1]);
dp2[v][j]=max(dp2[v][j-1],dp2[fa[v][j-1]][j-1]);
dp2[v][j]=max(dp2[v][j],mx[v][j-1]-mi[fa[v][j-1]][j-1]);
}
dfs(v,u);
}
}
int lca(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void init()
{
fill(mx[0],mx[n+1],-inf);
fill(mi[0],mi[n+1],inf);
fill(dp[0],dp[n+1],-inf);
fill(dp2[0],dp2[n+1],-inf);
dep[0]=0;
dfs(1,0);
}
int getmin(int u,int lca,int dp[][DEG])
{
int ans=inf;
int del=dep[u] - dep[lca];
for(int i=DEG-1;i>=0;i--)
if(del & (1<<i))
{
ans=min(ans,dp[u][i]);
u=fa[u][i];
}
return ans;
}
int getmax(int x,int lca,int dp[][DEG])
{
int ans=0;
int del=dep[x]-dep[lca];
for(int i=DEG-1;i>=0;i--)
if(del & (1<<i))
{
ans=max(ans,dp[x][i]);
x=fa[x][i];
}
return ans;
}
int gao(int x,int lca,int dp[][DEG])
{
int ans=0,tmp=0;
int del=dep[x]-dep[lca];
for(int i=0;i<DEG;i++)
if(del & (1<<i))
{
ans=max(ans,dp[x][i]);
ans=max(ans,tmp-mi[x][i]);
tmp=max(tmp,mx[x][i]);
x=fa[x][i];
}
return ans;
}
int gao2(int x,int lca,int dp[][DEG])
{
int ans=0,tmp=inf;
int del=dep[x]-dep[lca];
for(int i=DEG-1;i>=0;i--) if(del & (1<<i))
{
ans=max(ans,dp[x][i]);
ans=max(ans,-(tmp-mx[x][i]));
tmp=min(tmp,mi[x][i]);
x=fa[x][i];
}
return ans;
}
int solve(int x,int y)
{
int p=lca(x,y);
int a=gao2(x,p,dp);
int b=gao(y,p,dp2);
int c=getmin(x,p,mi);
int d=getmax(y,p,mx);
int ans=max(max(a,b),d-c);
return ans;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i,j,k,m;
while(~scanf("%d",&n))
{
memset(head,-1,sizeof(head));tol=0;
for(i=1;i<=n;i++)scanf("%d",&weight[i]);
for(i=1;i<n;i++)
{
scanf("%d%d",&j,&k);
add(j,k);
add(k,j);
}
init();
int Q;
scanf("%d",&Q);
while(Q--)
{
scanf("%d%d",&i,&j);
printf("%d\n",solve(i,j));
}
}
return 0;
}