CF1988D The Omnipotent Monster Killer 题解

题意简述

给定一棵 $n$ 个节点的树，节点 $i$ 有攻击力 $a_i$。进行 $10^{100}$ 轮战斗，每轮：

1. 所有存活的怪物攻击你，累计受到 $\sum a_{\text{存活}}$ 点伤害；
2. 你可以选择击杀若干怪物，但不能同时击杀相邻（有边直接相连）的两个怪物。

每轮均可做最优决策，求累计受到的最小总伤害。

由于轮数远大于 $n$，最终所有怪物都会被击杀，问题等价于给每个节点分配一个击杀轮次，使得相邻节点轮次不同，且最小化 $\sum a_i \cdot t_i$（$t_i$ 为节点 $i$ 被击杀的轮次，伤害累计 $t_i$ 次）。

---

两回合的情形

先看一个简化版：只有两回合。问题转化为每个节点选 $t_i \in \{1,2\}$，相邻节点不同。这是一个经典的树形 DP：

记 $f_{x,0/1}$ 表示节点 $x$ 在第 $1$ / 第 $2$ 回合被选中时，子树内总伤害的最小值。转移：

$$f_{x,0} = \sum_{y \in son_x} \min\{f_{y,0}, f_{y,1}\} $$$$f_{x,1} = a_x + \sum_{y \in son_x} f_{y,0}$$

---

扩展至多回合

对于 $+\infty$ 回合，将第二维换成节点被选中的回合编号 $i$。

设 $f_{x,i}$ 表示节点 $x$ 在第 $i$ 回合被选中时，$x$ 子树内怪物造成的总伤害最小值。则：

$$f_{x,i} = a_x \cdot i + \sum_{y \in son_x} \min_{j \neq i} f_{y,j} $$

即节点 $x$ 在第 $i$ 轮被击杀（承受 $i$ 次攻击），它的每个儿子 $y$ 需要选择一个与 $x$ 不同的轮次 $j$。

---

上界分析

若能证明存在一个较小的 $I$，使得任何最优解中所有节点的击杀轮次 $\le I$，则 DP 状态数为 $O(nI)$。

核心观察：考虑树上任意一条从某点到叶子的链。若存在连续 $3$ 个不相邻的节点均不被选择，中间节点可以拉一个不在该路径上的儿子"代替"自己承受伤害。通过这种"李代桃僵"的构造，可以得到：

一条相邻三点中至少有一个被选择的链，不选节点占比不超过 $\frac{4}{5}$。

每次删除这样的链，森林中每棵树递归操作，流程循环 $\lfloor\log_{\frac{5}{4}} n\rfloor + 1$ 次即可选完所有节点。计算得 $I \ge 57$ 即可覆盖 $n \le 3 \times 10^5$ 的情况。为保险可取 $I = 60$。

---

DP 转移优化

转移式中需要对每个儿子求 $\min_{j \neq i} f_{y,j}$。预处理好前缀最小值 pre 和后缀最小值 suf：

• pre[y][i] = $\min_{k \le i} f_{y,k}$
• suf[y][i] = $\min_{k \ge i} f_{y,k}$

于是：

$$\min_{j \neq i} f_{y,j} = \min(pre[y][i-1], \; suf[y][i+1]) $$

转移变为 $O(1)$，总复杂度 $O(nI)$。

---

复杂度

• 状态数：$O(nI)$，取 $I=60$ 即可。
• 转移：$O(1)$ 每次，总 $O(nI)$。
• 空间：$O(nI)$。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int inf = 1e18;

void solve() {
    int n, ans = inf;
    cin >> n;
    vector<int> a(n + 1);
    vector<vector<int>> adj(n + 1), f(n + 1, vector<int>(61)), pre, suf;
    pre = suf = f;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    auto dfs = [&](auto self, int x, int p) -> void {
        f[x][0] = f[x][60] = inf;
        for (int i = 1; i < 60; i++)
            f[x][i] = a[x] * i;

        for (auto y : adj[x]) {
            if (y == p) continue;
            self(self, y, x);
            for (int i = 1; i < 60; i++)
                f[x][i] += min(pre[y][i - 1], suf[y][i + 1]);
        }

        pre[x] = suf[x] = f[x];
        for (int i = 1; i <= 60; i++)
            pre[x][i] = min(pre[x][i], pre[x][i - 1]);
        for (int i = 59; i >= 0; i--)
            suf[x][i] = min(suf[x][i], suf[x][i + 1]);
    };

    dfs(dfs, 1, 1);
    for (int i = 1; i < 60; i++)
        ans = min(ans, f[1][i]);
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}