「一本通 5.2 例 4」战略游戏

形式化题目

给定一棵包含 $N$ 个节点的无向树（节点编号为 $0$ 到 $N - 1$ ）。要求在树上的某些节点放置士兵，如果一个节点放置了士兵，则与该节点相连的所有边都被瞭望（覆盖）。

求最少需要放置多少个士兵，才能使得树上的所有边都被至少一个士兵瞭望到。即求树的最小点覆盖（Minimum Vertex Cover）。

样例说明

输入样例：

text

对应一棵以节点 $0$ 或 $1$ 为中心相连的树：

节点 $0$ 连接 $1$
节点 $1$ 连接 $2, 3$
节点 $2, 3$ 没有子节点

树的边集为 $(0, 1), (1, 2), (1, 3)$ 。只需在节点 $1$ 放置 $1$ 名士兵，由于节点 $1$ 与节点 $0, 2, 3$ 都有边相连，所有 $3$ 条边都被覆盖。最少士兵数为 $1$ 。

graph TD
    0((0)) --- 1((1 [士兵]))
    1 --- 2((2))
    1 --- 3((3))

正解

思路

本题是树上经典的最小点覆盖问题。根据题意，对于树上的任意一条边 $(u, v)$ ，端点 $u$ 和 $v$ 中必须至少放置一个士兵，才能覆盖该边。

我们可以任选一个节点（如输入中入度为 0 的节点，或任意指定根）作为树根，将无向树转化为有向有根树。

1. 朴素思考与瓶颈

若采用搜索回溯枚举每个节点选或不选，共有 $2^N$ 种状态，当 $N$ 达到上千时复杂度为 $O(2^N)$ ，不可承受。

观察树的局部无后效性：对于以 $u$ 为根的子树，如果子树外的边如何被覆盖不影响子树内部结构，子树内部最优决策仅取决于节点 $u$ 本身是否放置了士兵。因此可以使用树形动态规划。

2. 状态定义

对于以 $u$ 为根的子树：

定义 $dp[u][0]$ 表示：节点 $u$ 不放置士兵时，覆盖以 $u$ 为根的子树内所有边所需的最少士兵数。
定义 $dp[u][1]$ 表示：节点 $u$ 放置士兵时，覆盖以 $u$ 为根的子树内所有边所需的最少士兵数。

3. 状态转移方程

对于节点 $u$ 的每一个子节点 $v$ ：

当 $u$ 不放置士兵（ $dp[u][0]$ ）时：连接边 $(u, v)$ 必须被覆盖，由于端点 $u$ 没有士兵，端点 $v$ 处必须放置士兵！此时子节点 $v$ 只能取状态 $dp[v][1]$ 。累加所有子节点贡献：
$dp[u][0] = \sum_{v \in sons(u)} dp[v][1]$
当 $u$ 放置士兵（ $dp[u][1]$ ）时：边 $(u, v)$ 已经由端点 $u$ 处的士兵覆盖。此时子节点 $v$ 处放不放士兵均可覆盖边 $(u, v)$ ，为了让子树所需总士兵数最少，子节点 $v$ 应取两种情况的较小值：
$dp[u][1] = 1 + \sum_{v \in sons(u)} \min(dp[v][0], dp[v][1])$
（初始时 $dp[u][1] = 1$ ，表示在节点 $u$ 放置了 1 名士兵）。

4. 计算顺序与实现细节

由于树形 DP 依赖于子节点的结果，我们需要按照自底向上（即树的后序遍历或拓扑逆序）依次转移。在 Python 中，如果树深度较大，使用深递归容易导致爆栈。可以使用栈进行自顶向下收集遍历序列（模拟 DFS），随后将遍历序列反转，得到逆拓扑序，直接做自底向上的迭代循环。

最终整棵树的答案为：

\min(dp[root][0], dp[root][1])

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-04-19 20:00
# update_at: 2026-04-19 20:00

import sys
from collections.abc import Iterator


def tree_min_vertex_cover(n: int, adj: list[list[int]], root: int = 0) -> int:
    """求以 root 为根的树的最小点覆盖大小。

    dp[u][0]: u 处不放士兵时，覆盖 u 为根的子树所有边所需的最少士兵数。
              此时 u 的所有子节点 v 处必须都放士兵。
    dp[u][1]: u 处放士兵时，覆盖 u 为根的子树所有边所需的最少士兵数。
              此时每个子节点 v 可以放也可以不放，取 min(dp[v][0], dp[v][1])。
    使用拓扑/DFS 后序模拟树形 DP，避免深递归爆栈。
    """
    order: list[int] = []
    parent = [-1] * n
    stack = [root]

    # BFS/DFS 收集自顶向下访问顺序
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v != parent[u]:
                parent[v] = u
                stack.append(v)

    # dp[u] = [不选 u, 选 u]
    dp0 = [0] * n
    dp1 = [1] * n

    # 逆拓扑序（自底向上）转移
    for u in reversed(order):
        for v in adj[u]:
            if v != parent[u]:
                dp0[u] += dp1[v]
                dp1[u] += min(dp0[v], dp1[v])

    return min(dp0[root], dp1[root])


def solve() -> None:
    tokens: Iterator[int] = map(int, sys.stdin.buffer.read().split())
    try:
        n = next(tokens)
    except StopIteration:
        return

    adj: list[list[int]] = [[] for _ in range(n)]
    in_degree = [0] * n

    for _ in range(n):
        u = next(tokens)
        k = next(tokens)
        children = [next(tokens) for _ in range(k)]
        adj[u].extend(children)
        for v in children:
            in_degree[v] += 1
            adj[v].append(u)

    # 找到树的根节点（输入中给出的父指向子，入度为 0 的即为树根）
    # 若有多棵树或全双向，任意找一个作为根；这里输入给的是有向树边，入度为 0 的节点即为根
    root = 0
    for i in range(n):
        if in_degree[i] == 0:
            root = i
            break

    ans = tree_min_vertex_cover(n, adj, root)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 09:49
 * update_at: 2026-10-05 09:49
 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 100005; // 节点数上限（本题 N 远小于此，留足余量）
vector<int> g[MAXN];     // g[u] 存与节点 u 相邻的所有节点，无向树双向加边
int parent_node[MAXN];   // parent_node[u]：以 root 为根时 u 的父亲，根的父亲记为 -1
int order[MAXN];         // 自顶向下的遍历顺序（正序为拓扑序，逆序即自底向上）
int stk[MAXN];           // 手动栈，替代递归 DFS，避免深树爆栈
int in_degree[MAXN];     // 输入中每条边只出现一次，入度为 0 的节点即为树根
ll dp0[MAXN];            // dp0[u]：u 不放士兵时，覆盖 u 子树内所有边的最少士兵数
ll dp1[MAXN];            // dp1[u]：u 放士兵时，覆盖 u 子树内所有边的最少士兵数

int main() {
    int n;
    if (scanf("%d", &n) != 1) {
        return 0;
    }

    for (int i = 0; i < n; i++) {
        int u, k;
        scanf("%d %d", &u, &k);
        for (int j = 0; j < k; j++) {
            int v;
            scanf("%d", &v);
            g[u].push_back(v);
            g[v].push_back(u);
            in_degree[v]++;
        }
    }

    // 输入给出的边由父指向子且每条边只出现一次，入度为 0 的节点就是树根
    int root = 0;
    for (int i = 0; i < n; i++) {
        if (in_degree[i] == 0) {
            root = i;
            break;
        }
    }

    // 显式栈做一遍 DFS，得到自顶向下的访问顺序
    for (int i = 0; i < n; i++) {
        parent_node[i] = -1;
    }
    int top = 0;
    stk[top++] = root;
    int order_cnt = 0;
    while (top > 0) {
        int u = stk[--top];
        order[order_cnt++] = u;
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            stk[top++] = v;
        }
    }

    // dp 初值：不选 u 至少要 0 人；选 u 则先记上 u 自己这 1 名士兵
    for (int i = 0; i < n; i++) {
        dp0[i] = 0;
        dp1[i] = 1;
    }

    // 逆拓扑序自底向上转移：
    // u 不选时，边 (u, v) 只能靠 v 覆盖，故子节点必须全选，取 dp1[v]；
    // u 选时，子节点 v 可选可不选，取 min(dp0[v], dp1[v])。
    for (int idx = order_cnt - 1; idx >= 0; idx--) {
        int u = order[idx];
        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_node[u]) {
                continue;
            }
            dp0[u] += dp1[v];
            dp1[u] += min(dp0[v], dp1[v]);
        }
    }

    printf("%lld\n", min(dp0[root], dp1[root]));
    return 0;
}

复杂度

时间复杂度： $\mathcal{O}(N)$ 。每个节点和每条树边在建树与自底向上的动态规划中仅被遍历常数次。
空间复杂度： $\mathcal{O}(N)$ 。邻接表、DP 数组及遍历栈的空间占用均为 $O(N)$ 。

总结

模型转化：将“瞭望所有路”精确刻画为图论中的“最小点覆盖”。在树形结构上，每条边的两个端点必须至少选一个。
两状态转移：当前节点不选时，所有子节点必须全选；当前节点选时，每个子节点取放或不放的极小值。
实现注意：树形 DP 使用显式栈收集逆拓扑序做迭代转移，可以彻底消除递归爆栈风险，在 Python 下运行效率高且代码精简。