洛谷P4657 [CEOI2017] Chase 题解

题目链接：P4657 [CEOI2017] Chase

题意：

在逃亡者的面前有一个迷宫，这个迷宫由 \(n\) 个房间和 \(n-1\) 条双向走廊构成，每条走廊会链接不同的两个房间，所有的房间都可以通过走廊互相到达。换句话说，这是一棵树。

逃亡者会选择一个房间进入迷宫，走过若干条走廊并走出迷宫，但他永远不会走重复的走廊。

在第 \(i\) 个房间里，有 \(F_i\) 个铁球，每当一个人经过这个房间时，他就会受到铁球的阻挡。逃亡者手里有 \(V\) 个磁铁，当他到达一个房间时，他可以选择丢下一个磁铁（也可以不丢），将与这个房间相邻的所有房间里的铁球吸引到这个房间。这个过程如下：

逃亡者进入房间。

逃亡者丢下磁铁。

逃亡者走出房间。

铁球被吸引到这个房间。

注意逃亡者只会受到这个房间原有的铁球的阻拦，而不会受到被吸引的铁球的阻挡。

在逃亡者走出迷宫后，追逐者将会沿着逃亡者走过的路径穿过迷宫，他会碰到这条路径上所有的铁球。

请帮助逃亡者选择一条路径，使得追逐者遇到的铁球数量减去逃亡者遇到的铁球数量最大化。

输入格式：

第一行两个空格隔开的整数整数 \(n\) 和 \(V\)。

第二行 \(n\) 个空格隔开的整数表示 \(F_i\)。

之后的 \(n-1\) 行，每行两个空格隔开的整数 \(x\) 和 \(y\)，表示有一条走廊连接编号为 \(x\) 和编号为 \(y\) 的房间。

输出格式：

输出一个整数表示最优情况下追逐者遇到的铁球数量减去逃亡者遇到的铁球数量。

数据范围：

\(1\le n\le 10^5,~0\le V\le 100,~0\le F_i\le 10^9\)。

本题有两种常见的dp方式，即换根dp 和 ~~朴素dp~~ 。

本文来讲一下朴素的做法吧，主要思想就是在每个节点统计横跨它的链的贡献。

考虑设 \(f(i,j,k),~g(i,j,k)\) 分别表示「从 \(i\) 到 \(i\) 子树」和「从 \(i\) 子树到 \(i\) 」选了 \(j\) 个的最大贡献，

其中 \(k=0\) 或 \(k=1\) 表示 \(i\) 有没有放磁铁，\(0\) 表示没有。

记 \(V_u\) 为 \(u\) 的儿子 \(v\) 的铁球个数 \(F_v\) 的和，即 \(V_u = \sum_{v \in \mathrm{son}(u)}F_v\) （后面代码里 \(F\) 写的是 \(a\) ）

考虑转移。对于儿子 \(v\) ，尝试以下更新（其中 \(\uparrow\) 表示「取max」） \[ \begin{aligned} &f(u,j,0) \operatorname{\big\uparrow} \max\left\{ f(v,j,0),~f(v,j,1)\right\} \\[6pt]& f(u,j,1) \operatorname{\big\uparrow} \max\left\{ f(v,j-1,0),~f(v,j-1,1)\right\} + V_u \\[6pt]& g(u,j,0) \operatorname{\big\uparrow} \max\left\{g(v,j,0),~g(v,j,1)\right\} \\[6pt]& g(u,j,1) \operatorname{\big\uparrow} \max\{g(v,j-1,0),~g(v,j-1,1)\} + V_u + F_{fa(u)} - F_v \end{aligned} \] 需要注意边界。统计答案的话在更新的过程中就可以了，合并前 \(u\) 的答案和 \(v\) 不会冲突。

时间复杂度 \(\mathcal{O}(nV)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))
#define M ((int)(114))

int n, m, res, pos = 1, a[N], val[N], head[N], f[N][M][2], g[N][M][2];
struct Edge { int v, next; } e[N * 2];
void addEdge(int u, int v) { e[++pos] = {v, head[u]}; head[u] = pos; }
void dfs(int u, int fa)
{
    val[u] = 0;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        dfs(v, u); val[u] += a[v];
    }
    f[u][0][1] = g[u][0][1] = -INF;
    up(g[u][1][1], val[u] + a[fa]);
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        int mx1 = 0, mx2 = 0;
        Rep(j, m, 0)
        {
            up(mx1, max(g[u][m - j][0], g[u][m - j][1]));
            up(mx2, max(f[u][m - j][0], f[u][m - j][1] + a[fa] - a[v]));
            up(res, max(f[v][j][0], f[v][j][1]) + mx1);
            up(res, max(g[v][j][0], g[v][j][1]) + mx2);
        }
        rep(j, 1, m)
        {
            up(f[u][j][0], max(f[v][j][0], f[v][j][1]));
            up(f[u][j][1], max(f[v][j - 1][0], f[v][j - 1][1]) + val[u]);
        }
        rep(j, 1, m)
        {
            up(g[u][j][0], max(g[v][j][0], g[v][j][1]));
            up(g[u][j][1], max(g[v][j - 1][0], g[v][j - 1][1]) + val[u] + a[fa] - a[v]);
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n - 1)
    {
        static int u, v; cin >> u >> v;
        addEdge(u, v); addEdge(v, u);
    }
    dfs(1, 0); cout << res << '\n';
    return 0;
}