LOJ6678 礼物

题目链接

思路

题目要求在树上求最短路，我们很容易想到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’ = 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/06/LOJ6678/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！