【LibreOJ】6678 礼物 题解

题目链接

思路

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

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

那么具体是什么呢？

• 假设我们从 $x$ 点出发，到达 $LCA(x, y)$ 的时候，进行了买入操作，在 $LCA(x, y)$ 到 $y$ 的路上进行了卖出操作，那么我们就需要知道 $x \to LCA(x, y)$ 上的最大值，$LCA(x, y) \to y$ 上的最小值。所以我们需要两个倍增数组：$maxF$ 维护最大值，$minF$ 维护最小值（比如 $maxF[x][i]$ 表示从 $x$ 到它的 $2^i$ 级祖先上最大值是多少）。

• 假如我们直接在 $x \to LCA(x, y)$ 进行了买入卖出操作，那么我们需要直接计算这个最大值。设 $up[x][i]$ 表示从 $x$ 到它的 $2^i$ 级祖先进行了先买后卖操作所能获得的最大值。那么怎么维护更新它呢？

  设 $y = f[x][i-1]$（中间点），最大值可能由以下三种情况中产生：

  • 在 $x \to y$ 中先买后卖，即 $up[x][i-1]$
  • 在 $y \to f[x][i]$ 中先买后卖，即 $up[y][i-1]$
  • 在 $x \to y$ 中买入，在 $y \to f[y][i-1]$ 中卖出，即 $maxF[y][i-1] - minF[x][i-1]$

• 在 $LCA(x, y) \to y$ 中进行先买后卖操作，我们新开一个 $down[x][i]$ 数组，含义与 $up$ 类似，但顺序不一样：表示从 $x$ 的 $2^i$ 级祖先到它本身，进行先买后卖操作。

一些细节

在求答案的过程中，使用这种方式遍历倍增数组。比如 $9 = 2^3 + 2^0$，那么就会先执行 $x’ = f[x][3]$，后执行 $x’’ = f[x’][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;
}