codevs 3305 水果姐逛水果街二
在倍增LCA的基础上做一些改进。
开四个二位数组ma，mi，premax，submax分别表示：从i到anc[i][...]的最大，最小值，从i到anc[i][...]的最大获利，从anc[i][...]到i的最大获利。
考虑如何更新？对于ma，mi，直接依照anc的方法进行更新即可。
对于premax，submax，则要再考虑行走方向，依据ma，mi进行更新。转移方程见方程。
考虑如何倍增求值？
令x,y的lca为z。分成从x到z，从y到z两步处理。
每次考虑运用ma配mi，premax或submax对ans进行更新，并记录maxx或minn值。
两步进行完之后，再maxx-minn与ans最后更新，即可得到正解。
注意？数组大小！！！！！！！！附上程序。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#define maxv 400050
#define maxe 400050
#define maxq 10050
using namespace std;
struct edge
{
long long v,nxt;
}e[maxe];
long long g[maxv]={0},n,m,x,y,price[maxv],nume=0;
long long ma[maxv][22]={0},mi[maxv][22],premax[maxv][22]={0},submax[maxv][22]={0},anc[maxv][22]={0};
long long dis[maxv]={0},ans=0;
bool vis[maxv]={false};
void addedge(long long u,long long v)
{
e[++nume].v=v;
e[nume].nxt=g[u];
g[u]=nume;
}
void dfs(long long u)
{
vis[u]=true;
for (long long i=g[u];i;i=e[i].nxt)
{
long long v=e[i].v;
if (vis[v]==false)
{
anc[v][0]=u;
ma[v][0]=max(price[v],price[u]);
mi[v][0]=min(price[v],price[u]);
premax[v][0]=price[u]-price[v];
submax[v][0]=price[v]-price[u];
dis[v]=dis[u]+1;
dfs(v);
}
}
}
long long lca(long long x,long long y)
{
if (dis[x]>dis[y]) swap(x,y);
for (long long i=14;i>=0;i--)
{
if (dis[anc[y][i]]>=dis[x])
y=anc[y][i];
}
for (long long i=14;i>=0;i--)
{
if (anc[x][i]!=anc[y][i])
{
x=anc[x][i];
y=anc[y][i];
}
}
if (x==y) return x;
else return anc[x][0];
}
void jump()
{
ans=0;
long long z=lca(x,y),minn=1234567,maxx=0;
long long t;
t=dis[x]-dis[z];
if (t>0)
{
for (long long i=14;i>=0;i--)
{
if (t>=(1<<i))//
{
t=t-(1<<i);
ans=max(premax[x][i],ans);
ans=max(ma[x][i]-minn,ans);
minn=min(minn,mi[x][i]);
x=anc[x][i];
}
}
}
t=dis[y]-dis[z];
if (t>0)
{
for (long long i=14;i>=0;i--)
{
if (t>=(1<<i))
{
t=t-(1<<i);
ans=max(submax[y][i],ans);
ans=max(ans,maxx-mi[y][i]);
maxx=max(maxx,ma[y][i]);
y=anc[y][i];
}
}
}
ans=max(ans,maxx-minn);
}
int main()
{
scanf("%lld",&n);
for (long long i=1;i<=n;i++)
scanf("%lld",&price[i]);
for (long long i=1;i<=n-1;i++)
{
scanf("%lld%lld",&x,&y);
addedge(x,y);
addedge(y,x);
}
dis[0]=-1;
dfs(1);
for (long long i=1;i<=14;i++)
for (long long j=1;j<=n;j++)
{
anc[j][i]=anc[anc[j][i-1]][i-1];
ma[j][i]=max(ma[j][i-1],ma[anc[j][i-1]][i-1]);
mi[j][i]=min(mi[j][i-1],mi[anc[j][i-1]][i-1]);
premax[j][i]=max(max(premax[j][i-1],premax[anc[j][i-1]][i-1]),ma[anc[j][i-1]][i-1]-mi[j][i-1]);
submax[j][i]=max(max(submax[j][i-1],submax[anc[j][i-1]][i-1]),ma[j][i-1]-mi[anc[j][i-1]][i-1]);
}
scanf("%lld",&m);
for (long long i=1;i<=m;i++)
{
scanf("%lld%lld",&x,&y);
jump();
printf("%lld
",ans);
}
return 0;
}