提高培优班套题训练10T3题解
题意简述
给定一棵有 n 个带点权节点的树，求从 x 到 y 的路径上的最大收益（不能回溯）。
思路
首先，我们考虑暴力。
直接从 x 暴力跳到 lca 并维护当前最小值，同时计算当前值与最小值的差取 max 。
同理，y做反向操作。最后再把两边维护的 max-min 和 ans 取 max ，就能得到最终答案。
没错这样写就能得到100分的好成绩
在暴力过程中，我们发现，时间复杂度都叠在遍历整个链，那怎么减少这个复杂度呢？
我们可以考虑类似于倍增跳 lca 的方式去计算。
那我们要维护的东西也就推出来了：
- f_{i,j} 表示 i 节点向上跳 2^j 步的节点编号（找 lca）
- ma_{i,j} 表示 i 节点向上跳 2^j 步的最大点权
- mi_{i,j} 表示 i 节点向上跳 2^j 步的最小点权（暴力的时候，维护的当前最小、最大）
- retup_{i,j} 表示 i 节点向上跳 2^j 步向上走的贡献（即从 x 出发的贡献）
- retdown_{i,j} 表示 i 节点向上跳 2^j 步向下走的贡献（即从 y 出发的贡献）
那么难点应该就集中在 retup 和 retdown 的转移上。
以 retup 为例，
假设，我们 x 已经跳到新的位置，并计算好当前我们所需维护的东西，并且下一步就要跳到 lca 了（显然其他位置也是同理的）。
那么 f_{x,j}=lca 。
令 t 为 lca 和 x 的中点，即 f_{x,j-1}=t 。
那么，答案一共有三种情况：
- 取的两点都在 x\to t 的链上，贡献就是 retup_{x,j-1}
- 取的两点都在 t\to lca 的链的链上，贡献就是 retup_{t,j-1} 。
- 取的两点分别在$x\to t$ 和$t\to lca$ 的链上，贡献就是 ma_{t,j-1}-mi_{x,j-1} 。
这三种直接取 max 就好了。
最终计算答案和 retdown 也是相似的情况，就不多赘述了，详见代码吧。
code
int n,m,s;
vector<int>e[N];
int f[20][N],dep[N],a[N];
int ma[20][N],mi[20][N],retdown[20][N],retup[20][N];
inline void dfs(int u,int fa){
dep[u]=dep[fa]+1;f[0][u]=fa;
ma[0][u]=max(a[u],a[fa]);mi[0][u]=min(a[u],fa==0?0x7fffffff:a[fa]);
retdown[0][u]=a[u]-(fa==0?0x7fffffff:a[fa]);retup[0][u]=a[fa]-a[u];
for(int a=1;a<=19;++a) f[a][u]=f[a-1][f[a-1][u]],ma[a][u]=max(ma[a-1][u],ma[a-1][f[a-1][u]]),
mi[a][u]=min(mi[a-1][u],mi[a-1][f[a-1][u]]),
retdown[a][u]=max(ma[a-1][u]-mi[a-1][f[a-1][u]],max(retdown[a-1][u],retdown[a-1][f[a-1][u]])),
retup[a][u]=max(ma[a-1][f[a-1][u]]-mi[a-1][u],max(retup[a-1][u],retup[a-1][f[a-1][u]]));
for(const int &v:e[u]){
if(v==fa)continue;
dfs(v,u);
}
}
inline int lca(int x,int y){
if(dep[x]<dep[y])x^=y^=x^=y;
for(int a=19;~a;--a)
if(dep[f[a][x]]>=dep[y]) x=f[a][x];
if(x==y) return x;
for(int a=19;~a;--a)
if(f[a][x]^f[a][y])
x=f[a][x],y=f[a][y];
return f[0][x];
}
signed main(){
read(n);
for(int i=1;i<=n;i++)read(a[i]);
for(int i=1,x,y;i<n;i++) {
read(x,y);
e[x].emplace_back(y),e[y].emplace_back(x);
}
read(m);
dfs(1,0);
int x,y,LCA,ans,max_,min_,X,Y;
while(m--){
read(x,y);LCA=lca(x,y);ans=0;max_=-1;min_=0x7fffffff;X=x,Y=y;
if(x==y){puts("0");continue;}
if(x!=LCA){
for(int a=19;~a;--a){
if(dep[f[a][x]]>=dep[LCA]){
ans=max(max(ma[a][x]-min_,retup[a][x]),ans);
// printf("(ma[a][x]:%d min:%d)\n",ma[a][x],min_);
// printf("retup:%d a:%d x:%d\n",retup[a][x],a,x);
min_=min(min_,mi[a][x]);
x=f[a][x];
}
}
// printf("<1:%d>\n",ans);
}
if(y!=LCA){
for(int a=19;~a;--a){
if(dep[f[a][y]]>=dep[LCA]){
ans=max(max(max_-mi[a][y],retdown[a][y]),ans);
// printf("(mi[a][x]:%d max:%d)\n",mi[a][x],max_);
// printf("retdown:%d a:%d y:%d\n",retdown[a][y],a,y);
max_=max(max_,ma[a][y]);
y=f[a][y];
}
}
// printf("<2:%d>\n",ans);
}
if(X!=LCA&&Y!=LCA){
ans=max(ans,max_-min_);
// printf("<3:%d>\n",ans);
}
printf("%d\n",ans);
}
return 0;
}