你好！我是你的OI教练。

这是 P2016 战略游戏 的标准 AC 代码。

这道题是最小点覆盖的模板题。代码结构与上一道《没有上司的舞会》非常相似，区别在于状态转移的逻辑（取 min 还是 sum）以及初始化的代价（放士兵要花费 1）。

为了保证代码的鲁棒性（Robustness），我加入了一个简单的“找根”逻辑，防止测试数据中根节点不是 0 的情况（虽然本题大部分数据根是 0，但在竞赛中严谨一点总没错）。

核心代码 (C++14 NOIP标准)

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 memset

using namespace std;

// 数据规模：N <= 1500，开 1505 足够
const int MAXN = 1505;

// dp[u][0]: u 节点【不放】士兵，以 u 为根的子树全部被覆盖的最小士兵数
// dp[u][1]: u 节点【放】士兵，以 u 为根的子树全部被覆盖的最小士兵数
int dp[MAXN][2];

// 邻接表存图
vector<int> adj[MAXN];

// 用来寻找根节点（没有父亲的节点即为根）
bool has_parent[MAXN];

// 深度优先搜索 (Tree DP)
void dfs(int u) {
    // ================= 初始化 =================
    // 1. 如果 u 不放士兵，初始花费为 0
    dp[u][0] = 0;
    // 2. 如果 u 放士兵，初始花费为 1 (因为他自己就是一个士兵)
    dp[u][1] = 1;

    // ================= 遍历子节点 =================
    for (int v : adj[u]) {
        dfs(v); // 递归，先计算子树的状态

        // ================= 状态转移 =================
        
        // 情况 1: 父节点 u 【不放】士兵 (dp[u][0])
        // 逻辑：为了覆盖边 (u, v)，既然 u 没放，子节点 v 【必须放】
        dp[u][0] += dp[v][1];

        // 情况 2: 父节点 u 【放】士兵 (dp[u][1])
        // 逻辑：边 (u, v) 已经被 u 覆盖了。
        // 子节点 v 放不放都可以，为了总数最少，我们取 v 放或不放中的【最小值】
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

int main() {
    // 竞赛标准 IO 优化
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    if (!(cin >> n)) return 0;

    // 多组数据的题目通常需要 memset 清空，本题只有一组数据，这步可省，但习惯要好
    memset(has_parent, 0, sizeof(has_parent));

    // 处理输入
    // 输入格式：节点标号 u, 后面跟着 k 个子节点
    for (int i = 0; i < n; i++) {
        int u, k;
        cin >> u >> k; // 读入当前节点 u 和它的邻居数量 k
        
        while (k--) {
            int v;
            cin >> v;
            adj[u].push_back(v); // 建立边 u -> v
            has_parent[v] = true; // 标记 v 是有父亲的
        }
    }

    // 寻找根节点
    // 根节点是唯一一个没有被标记为“有父亲”的节点
    int root = 0;
    for (int i = 0; i < n; i++) {
        if (!has_parent[i]) {
            root = i;
            break;
        }
    }

    // 开始 DP
    dfs(root);

    // 最终答案
    // 根节点无论是放还是不放，只要能覆盖全树，取最小值即可
    cout << min(dp[root][0], dp[root][1]) << endl;

    return 0;
}

👨‍🏫 教练划重点（关键点与易错点）

1. 状态初始值的区别：

   • 在《舞会》题中，选人获得的权值是 $r_i$。
   • 在这道《战略游戏》中，每个士兵的权值是 1。
   • 易错点：很多人习惯写 dp[u][1] = 0，忘记加上当前这个士兵的一条命，导致结果偏小。记得初始化 dp[u][1] = 1。

2. 输入格式的处理：

   • 这题的输入有点“啰嗦”。它不是简单的 u v 一行行给，而是 u k v1 v2 ...。
   • 代码中使用了 while(k--) 来循环读取子节点，这是处理变长参数输入的常用技巧。

3. 找根的必要性：

   • 虽然题目没明说根是 0，且输入像是给的有向图（父亲指向儿子），但为了代码严谨，我们用 has_parent 数组统计入度。入度为 0 的就是根。这样无论数据怎么打乱顺序（比如先输入叶子再输入根），程序都能正确运行。

4. 逻辑对比（背诵口诀）：

   • 最大独立集（舞会）：父去子不去，父不去子随意（取max）。
   • 最小点覆盖（战略）：父无子必须，父有子随意（取min）。

这套模板非常通用，掌握好这两个 DP 方程，你已经半只脚踏进树形 DP 的大门了！加油！

你好！我是你的OI教练。很高兴你已经完成了“没有上司的舞会”，现在我们来攻克它的兄弟题——《战略游戏》。

这两道题简直是树形DP的双子星。

• 上一题（舞会）是求“最大独立集”（互不冲突的点权之和最大）。
• 这一题（战略游戏）是求“最小点覆盖”（用最少的点覆盖所有的边）。

虽然名字听起来很高大上，但核心逻辑依然是：子节点的状态决定父节点的状态。

第一部分：思路提示

1. 题目翻译（人话版）： 我们要在这棵树的节点上放士兵。 如果我在节点 $u$ 放了一个士兵，那么跟 $u$ 相连的所有“路”（边）都被看守住了。 目标：花最少的士兵，把整棵树所有的边都看守住。

2. 核心矛盾： 对于一条边 $(u, v)$ （$u$ 是爸爸，$v$ 是儿子）： 要想看守住这条边，$u$ 和 $v$ 两人中，至少得有一个人放士兵。

3. 对比“舞会”题：

• 舞会：如果爸爸去了，儿子绝不能去；如果爸爸没去，儿子随便。
• 战略游戏：如果爸爸没放士兵，儿子必须放（否则这条边没人管）；如果爸爸放了，儿子随便（反正边已经由爸爸管了，儿子放不放取决于他下面的边）。

发现了吗？逻辑刚刚好是反过来的！

第二部分：预备知识点总结

1. 树的存储：
   • 题目输入虽然说是无根树，但给出的格式“每条边只出现一次”，其实暗示了父子关系（或者我们可以把它当成以 0 为根的树）。
   • 输入格式是：节点标号 邻居数量 邻居1 邻居2...。
   • 可以使用 vector<int> adj[N] 存图。
2. 状态定义：
   • $dp[u][0]$：节点 $u$ 不放士兵，以 $u$ 为根的子树全部被覆盖的最小代价。
   • $dp[u][1]$：节点 $u$ 放士兵，以 $u$ 为根的子树全部被覆盖的最小代价。
3. DFS 后序遍历：依然是先处理子节点，回溯时更新父节点。

第三部分：启发式教学 —— 草稿纸上的推演

拿出草稿纸，我们画一个简单的父子结构，来推导状态转移方程。

场景图示：

      u (爸爸)
      |
      | <--- 这条边必须被覆盖
      |
      v (儿子)

推演 1：计算 $dp[u][0]$（爸爸 $u$ 不放士兵）

• 花费：首先，$u$ 自己不放，花费是 0。
• 约束：看向边 $(u, v)$。既然爸爸 $u$ 没放，那为了覆盖这条边，儿子 $v$ 必须放士兵！
• 子节点贡献：对于 $u$ 的每一个儿子 $v$，我们别无选择，只能加上 $dp[v][1]$。
• 方程雏形：$$dp[u][0] = 0 + \sum (dp[v][1])$$

推演 2：计算 $dp[u][1]$（爸爸 $u$ 放士兵）

• 花费：首先，$u$ 自己放了，花费是 1。
• 约束：看向边 $(u, v)$。因为爸爸 $u$ 已经放了，这条边已经被覆盖了。
• 自由度：儿子 $v$ 放不放都可以。
  • 如果儿子放 ($dp[v][1]$)，可能是因为儿子下面还有孙子需要他管。
  • 如果儿子不放 ($dp[v][0]$)，反正他和 $u$ 的边已经搞定了。
  • 我们要总士兵最少，所以取两者中较小的那个。
• 方程雏形：$$dp[u][1] = 1 + \sum (\min(dp[v][0], dp[v][1]))$$

第四部分：实战模拟（样例）

输入数据：

4
0 1 1   (0号点连着1) -> 0是根
1 2 2 3 (1号点连着2, 3)
2 0     (2号点没子节点)
3 0     (3号点没子节点)

树结构：

    0
    |
    1
   / \
  2   3

DP 计算过程（自底向上）：

1. 叶子节点 2 和 3：

   • $dp[2][0]$ (不放)：0
   • $dp[2][1]$ (放)：1
   • $dp[3][0]$：0
   • $dp[3][1]$：1

2. 节点 1 (子节点是 2, 3)：

   • $dp[1][0]$ (1不放)：
     • 儿子必须放。
     • $= 0 + dp[2][1] + dp[3][1] = 0 + 1 + 1 = 2$。
   • $dp[1][1]$ (1放)：
     • 儿子随便，取最小。
     • $= 1 + \min(dp[2][0], dp[2][1]) + \min(dp[3][0], dp[3][1])$
     • $= 1 + \min(0, 1) + \min(0, 1)$
     • $= 1 + 0 + 0 = 1$。
   • 此时节点1状态：不放代价2，放代价1。

3. 根节点 0 (子节点是 1)：

   • $dp[0][0]$ (0不放)：
     • 儿子1必须放。
     • $= 0 + dp[1][1] = 0 + 1 = 1$。
   • $dp[0][1]$ (0放)：
     • 儿子1随便。
     • $= 1 + \min(dp[1][0], dp[1][1])$
     • $= 1 + \min(2, 1) = 1 + 1 = 2$。

最终答案： $\min(dp[0][0], dp[0][1]) = \min(1, 2) = 1$。 与样例输出一致！

教练的最后叮嘱：

1. 输入坑点：这题的输入有点“古老”。注意看第二行开始：节点标号 k k个邻居。你需要写两层循环来读入。
2. 节点编号：节点是 $0$ 到 $n-1$。根节点通常是 0（或者入度为0的点，但这题无向边其实任意点做根都行，习惯用 0）。
3. 初始化：
   • 每次计算 $u$ 时，$dp[u][0] = 0$， $dp[u][1] = 1$（因为自己放了一个兵）。

现在，试着把这个逻辑写成代码吧！你会发现它和上一题的代码结构有 90% 是相似的。加油！