wyh的商机_牛客博客

很直接的一个想法就是把 $x,y$ 的 $LCA$ 作为断点，将整个链 $x-y$ 切分为两段 $x-LCA,LCA-y$ 。

那么只有三种情况：

在 $x-LCA$ 买卖
在 $LCA-y$ 买卖
在 $x-LCA$ 买，在 $LCA-y$ 卖

求 $LCA$ 就交给了倍增，因为树剖后面还要写数据结构维护，比较麻烦。。。

（当然离线 $Tarjan$ 也可做）

维护四个值：

$maxn[i][j]:\text{从i向上跳}2^j\text{步的最大权值}\\$ $minn[i][j]:\text{从i向上跳}2^j\text{步的最小权值}\\$ $upon[i][j]:\text{从i向上跳}2^j\text{步进行买卖能获得的最大利益}\\$ $down[i][j]:\text{从i向上跳}2^j\text{步反向进行买卖能获得的最大利益}\\$

前两个很显然的维护方式，跟着倍增一起跳就好。

后面两个维护是和求解方式差不多的思路，也就是把 $i-f[i][j](\text{i向上跳}2^j\text{步})$ 拆成 $i-f[i][j-1],f[i][j-1]-f[i][j]$ ，仍然是上述三种情况。

这样维护的式子就出来了：（ $v=f[u][j-1],w=f[v][j-1]=f[u][j]$ ）

$upon[u][j]=\max(\max(upon[u][j-1],upon[v][j-1]),maxn[v][j-1]-minn[u][j-1])\\$ $down[u][j]=\max(\max(down[u][j-1],down[v][j-1]),maxn[u][j-1]-minn[v][j-1])\\$

最终答案的式子同理。

防止溢出建议开 $long\ long$ 。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 50010
#define MAX (1LL<<62)
using namespace std;
int n,q,c=1;
int head[MAXN],deep[MAXN],f[MAXN][20];
long long val[MAXN],maxn[MAXN][20],minn[MAXN][20],upon[MAXN][20],down[MAXN][20];
struct Tree{
    int next,to;
}tree[MAXN<<1];
char tp[100000],*p1=tp,*p2=tp;
inline char get_char(){
    return p1==p2&&(p2=(p1=tp)+fread(tp,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=get_char();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=get_char();}
    return date*w;
}
inline void addedge(int x,int y){
    tree[c].to=y;tree[c].next=head[x];head[x]=c++;
    tree[c].to=x;tree[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
    for(int i=head[rt],will;i;i=tree[i].next){
        will=tree[i].to;
        if(!deep[will]){
            deep[will]=deep[rt]+1;
            f[will][0]=rt;
            maxn[will][0]=max(val[rt],val[will]);
            minn[will][0]=min(val[rt],val[will]);
            upon[will][0]=max(val[rt]-val[will],0LL);
            down[will][0]=max(val[will]-val[rt],0LL);
            dfs(will);
        }
    }
}
void step(){
    for(int j=1;j<=19;j++)for(int i=1,k;i<=n;i++){
        f[i][j]=f[f[i][j-1]][j-1];
        k=f[i][j-1];
        maxn[i][j]=max(maxn[i][j-1],maxn[k][j-1]);
        minn[i][j]=min(minn[i][j-1],minn[k][j-1]);
        upon[i][j]=max(maxn[k][j-1]-minn[i][j-1],max(upon[i][j-1],upon[k][j-1]));
        down[i][j]=max(maxn[i][j-1]-minn[k][j-1],max(down[i][j-1],down[k][j-1]));
    }
}
int LCA(int x,int y){
    if(deep[x]<deep[y])swap(x,y);
    for(int i=19;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];
    if(x==y)return x;
    for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
    return f[x][0];
}
long long query(int x,int y,int lca){
    long long front=MAX,after=0,s=0;
    for(int i=19;i>=0;i--){
        if((deep[x]-deep[lca])&(1<<i)){
            s=max(s,max(upon[x][i],maxn[x][i]-front));
            front=min(front,minn[x][i]);
            x=f[x][i];
        }
        if((deep[y]-deep[lca])&(1<<i)){
            s=max(s,max(down[y][i],after-minn[y][i]));
            after=max(after,maxn[y][i]);
            y=f[y][i];
        }
    }
    return 1LL*max(s,after-front);
}
void work(){
    int x,y,lca;
    q=read();
    while(q--){
        x=read();y=read();
        lca=LCA(x,y);
        printf("%lld\n",query(x,y,lca));
    }
}
void init(){
    n=read();
    for(int i=1;i<=n;i++)val[i]=read();
    for(int i=1,x,y;i<n;i++){
        x=read();y=read();
        addedge(x,y);
    }
    deep[1]=1;
    dfs(1);
    step();
}
int main(){
    init();
    work();
    return 0;
}