UVa 12452 Plants vs. Zombies HD SP

题目描述

给定一棵包含 $N$ 个顶点的树（$2\le N\le 10,000$），僵尸位于树的边上。我们需要在顶点上种植植物来保护所有边，每条边至少被一个顶点上的植物覆盖。每个顶点最多种植一株植物。植物共有三种：

• 豌豆射手（$\text{Peashooter}$）：成本 $100$，可以覆盖该顶点相邻的任意一条边。
• 分裂豌豆（$\text{Split Pea}$）：成本 $175$，可以覆盖该顶点相邻的任意两条边。
• 杨桃（$\text{Starfruit}$）：成本 $500$，可以覆盖该顶点相邻的所有边。

目标：选择一组顶点种植植物，使得每条边至少被覆盖一次，且总成本最小。

题目分析

这是一个树上最小权顶点覆盖的变种问题。与经典顶点覆盖不同，每个顶点可以覆盖其邻边中的一部分（取决于所种植物），且覆盖能力有限。需要为每个顶点决定：

• 是否种植植物
• 种植哪种植物
• 植物覆盖哪些邻边（豌豆和分裂需要选择）

由于树的结构，我们可以采用树形动态规划（$\text{DFS}$）自底向上求解。

解题思路

状态定义

对于每个节点 $u$，考虑它与父节点之间的边 $(u,parent)$。这条边有两种状态：

• 被 $u$ 覆盖
• 不被 $u$ 覆盖（由父节点覆盖）

因此定义：

• $dp[u][0]$：在以 $u$ 为根的子树中，$u$ 不覆盖边 $(u,parent)$ 的最小代价
• $dp[u][1]$：在以 $u$ 为根的子树中，$u$ 覆盖边 $(u,parent)$ 的最小代价

其中 $parent$ 是 $u$ 在 $\text{DFS}$ 树中的父节点。对于根节点，没有父边，最终答案取 $\min (dp[root][0],dp[root][1])$。

子节点预处理

考虑节点 $u$ 的所有子节点 $v$（$v\ne parent$）。对每个子节点 $v$，我们已经递归计算出 $dp[v][0]$ 和 $dp[v][1]$。

定义：

• $c_{1_v}=dp[v][1]$：子节点 $v$ 覆盖边 $(u,v)$ 的代价
• $c_{0_v}=dp[v][0]$：子节点 $v$ 不覆盖边 $(u,v)$ 的代价
• $dif{f}_v=c_{1_v}-c_{0_v}$：$v$ 从“不覆盖父边”切换到“覆盖父边”的额外代价（可能为负）

贪心选择策略

当节点 $u$ 需要选择覆盖某些子边时，应优先选择 $dif{f}_v$ 最大的子节点，因为让 $u$ 覆盖这些边能节省最多代价。因此需要对所有子节点的 $diff$ 值排序，取最大的若干个。

状态转移

1. 不种植植物

如果 $u$ 不种植物，它无法覆盖任何边，因此：

• 它不可能覆盖父边：$dp[u][1]$ 不可行（保持无穷大）
• 边 $(u,v)$ 必须由子节点 $v$ 覆盖：$dp[u][0]=\sum c_{1_v}$

2. 种植豌豆射手（成本 $100$，覆盖 $1$ 条边）

• 覆盖父边：豌豆用于覆盖父边，所有子边由子节点覆盖
  $dp[u][1]=100+\sum c_{1_v}$

• 不覆盖父边：豌豆用于覆盖一条子边，剩余子边由子节点覆盖
  选择 $diff$ 最大的子节点 $v_{max}$，由 $u$ 覆盖该边
  该子节点从 $c_1$ 切换为 $c_0$，代价减少 $dif{f}_{max}$
  $dp[u][0]=100+\sum c_{1_v}-dif{f}_{max}$

3. 种植分裂豌豆（成本 $175$，覆盖 $2$ 条边）

• 覆盖父边 + 一条子边：父边被覆盖，再选一条子边由 $u$ 覆盖
  $dp[u][1]=175+\sum c_{1_v}-dif{f}_{max}$

• 不覆盖父边 + 两条子边：选两条子边由 $u$ 覆盖
  选择 $diff$ 最大的两个子节点 $v_{max1}$、$v_{max2}$
  $dp[u][0]=175+\sum c_{1_v}-dif{f}_{max1}-dif{f}_{max2}$

4. 种植杨桃（成本 $500$，覆盖所有邻边）

杨桃覆盖父边和所有子边，因此：

• $dp[u][1]=500+\sum \min (c_{0_v},c_{1_v})$

注意：对于子节点 $v$，边 $(u,v)$ 已被 $u$ 覆盖，$v$ 可以自由选择是否覆盖父边，因此取 $\min (c_{0_v},c_{1_v})$。

• $dp[u][0]$ 不可能，因为杨桃必定覆盖父边。

叶子节点处理

当 $u$ 是叶子节点（无子节点）时：

• $dp[u][0]=0$：不覆盖父边，子树内无边需要覆盖
• $dp[u][1]=100$：覆盖父边，只能种植豌豆（成本 $100$）

根节点处理

根节点没有父边，因此 $dp[root][0]$ 和 $dp[root][1]$ 都合法，最终答案取 $\min (dp[root][0],dp[root][1])$。

算法复杂度

• 每个节点访问一次，对子节点排序 $O(deg(u)\log deg(u))$
• 总复杂度 $O(N\log N)$，对于 $N\le 10,000$ 足够快。

代码实现

// Plants vs. Zombies HD SP
// UVa ID: 12452
// Verdict: Accepted
// Submission Date: 2026-05-27
// UVa Run Time: 0.010s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 10005;

vector<int> G[MAXN];
int dp[MAXN][2];
int cost[4] = {0, 100, 175, 500};

void dfs(int u, int parent) {
dp[u][0] = dp[u][1] = INF;
bool isLeaf = true;
int sum1 = 0; // 所有子节点取 dp[v][1] 的和
int sum3 = 0; // 所有子节点取 min(dp[v][0], dp[v][1]) 的和
int maxDiff = 0, maxDiff2 = 0; // 最大的两个差值 dp[v][1] – dp[v][0]

for (int v : G[u]) if (v != parent) {
isLeaf = false;
dfs(v, u);
sum1 += dp[v][1];
sum3 += min(dp[v][0], dp[v][1]);
int diff = dp[v][1] – dp[v][0];
if (diff > maxDiff2) {
maxDiff2 = diff;
if (maxDiff2 > maxDiff) swap(maxDiff, maxDiff2);
}
}

// 叶子节点
if (isLeaf) {
dp[u][0] = 0;
dp[u][1] = cost[1];
return;
}

// dp[u][0]: 不覆盖父边
// 豌豆：覆盖1条子边
dp[u][0] = sum1 – maxDiff + cost[1];
// 分裂：覆盖2条子边
if (maxDiff2 > 0) // 需要两个不同的子节点
dp[u][0] = min(dp[u][0], sum1 – maxDiff – maxDiff2 + cost[2]);
// 不放植物：所有子边由子节点覆盖
dp[u][0] = min(dp[u][0], sum1);

// dp[u][1]: 覆盖父边
// 豌豆：覆盖父边
dp[u][1] = sum1 + cost[1];
// 分裂：覆盖父边 + 1条子边
dp[u][1] = min(dp[u][1], sum1 – maxDiff + cost[2]);
// 杨桃：覆盖所有边
dp[u][1] = min(dp[u][1], sum3 + cost[3]);
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);

int T;
cin >> T;
while (T—) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) G[i].clear();
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
dfs(0, –1);
cout << "$" << min(dp[0][0], dp[0][1]) << "\\n";
}
return 0;
}

总结

本题的关键在于：

这种树形 $\text{DP}$ 结合贪心选择的方法，是解决树上资源分配问题的常用技巧。