【LibreOJ 】6678 礼物 题解

题目链接

思路

题目要求在树上求最短路，我们很容易想到LCA来解决。

但问题我们需要同时计算能获得的最大值，所以我们需要额外的倍增数组来维护一些值。

那么具体是什么呢？

• 假设我们从$x$点出发，到达$LCA(x,y)$的时候，进行了买入操作，在$LCA(x,y)$到$y$的路上，进行了卖出操作，那么我们就需要直到$x?LCA(x,y)$上的最大值，$LCA(x,y)?y$上的最小值。所以我们需要两个倍增数组，一个$maxF$维护最大值，一个位置最小值$minF$(比如$maxF[x][i]$表示从$x$到它的$i$级祖先上最大值是多少)
• 假如我们直接在$x?LCA(x,y)$进行了买入卖出操作，那么我们需要直接计算这个最大值，设$up[x][i]$表示从$x$到它的$i$祖先进行了先买后卖操作所能获得最大值。那么我们怎么维护更新它呢？
  设$y=f[x][i?1]$,那么最大值可能由以下三种情况中产生:
  • 在$x?y$中先卖后买，即$up[x][i?1]$
  • 在$y?f[x][i]$中先买后卖，即$up[y][i?1]$
  • 在$x?y$中买入，在$y?f[y][i?1]$中卖出，即$maxF[x][i?1]?minF[x][i?1]$
• 在$LCA(x,y)?y$中进行先买后卖操作，我们新开一个$down[x][i]$数组，含义与$up$类似，但注意，顺序不一样，这个表示从$x$的$i$级祖先到它本身，进行先买后卖操作。

一些细节

在求答案的过程中，使用了这种方式遍历倍增数组。
比如$9=2^3+2^0$,那么就会先执行$x^{\prime }=f[x][3]$,后执行$x^{\prime \prime }=f[x^{\prime }][0]$

for(int i = 20; i >= 0; --i)if(dep & (1 << i)) {
     ans = max(ans, max(up[x][i], maxF[x][i] - minNum));minNum = min(minNum, minF[x][i]);x = f[x][i];}

代码

#include <cstdio>
#include <iostream>
using namespace std;const int maxN = 3e5 + 7;struct Edge {
    int from, to;
}e[maxN << 1];int n, m, head[maxN], cnt, val[maxN], f[maxN][31], d[maxN], minF[maxN][31], maxF[maxN][31], up[maxN][31], down[maxN][31];inline void add(int u, int v)
{
    e[++cnt].from = head[u];e[cnt].to = v; head[u] = cnt;
}void dfs(int x, int fa)
{
    d[x] = d[fa] + 1; f[x][0] = fa;maxF[x][0] = max(val[x], val[fa]); minF[x][0] = min(val[x], val[fa]);up[x][0] = max(0, val[fa] - val[x]); down[x][0] = max(0, val[x] - val[fa]);for(int i = 1; i <= 20; ++i) {
    f[x][i] = f[f[x][i - 1]][i - 1];if(!f[x][i])break;int y = f[x][i - 1];maxF[x][i] = max(maxF[x][i - 1], maxF[y][i - 1]);minF[x][i] = min(minF[x][i - 1], minF[y][i - 1]);up[x][i] = max(max(up[x][i - 1], up[y][i - 1]), maxF[y][i - 1] - minF[x][i - 1]);down[x][i] = max(max(down[x][i - 1], down[y][i - 1]), maxF[x][i - 1] - minF[y][i -1]);}for(int i = head[x]; i; i = e[i].from) {
    int y = e[i].to;if(y == fa)continue;dfs(y, x);}
}inline int Lca(int x, int y)
{
    if(d[x] > d[y])swap(x, y);for(int i = 21; i >= 0; --i)if(d[f[y][i]] >= d[x])y = f[y][i];if(x == y)return x;for(int i = 21; i >= 0; --i)if(f[x][i] != f[y][i])x = f[x][i], y = f[y][i];return f[x][0];
}inline int query(int x, int y)
{
    int lca = Lca(x, y), ans = 0, maxNum = 0, minNum = 0x3f3f3f3f;int dep = d[x] - d[lca];if(dep) {
     // 如果x不是lca(x,y)for(int i = 20; i >= 0; --i)if(dep & (1 << i)) {
     ans = max(ans, max(up[x][i], maxF[x][i] - minNum));minNum = min(minNum, minF[x][i]);x = f[x][i];}}dep = d[y] - d[lca];if(dep) {
    for(int i = 20; i >= 0; --i)if(dep & (1 << i)) {
    ans = max(ans, max(down[y][i], maxNum - minF[y][i]));maxNum = max(maxNum, maxF[y][i]);y = f[y][i];}        }return max(ans, maxNum - minNum);
}int main()
{
    scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d", &val[i]);for(int i = 1; i < n; ++i) {
    int x, y; scanf("%d%d", &x, &y);add(x, y); add(y, x);}dfs(1, 0);scanf("%d", &m);for(int i = 1; i <= m; ++i) {
    int x, y; scanf("%d%d", &x, &y);printf("%d\n", query(x, y));}return 0;
}