[SEERC 2000] 战略游戏

形式化题目

给定一棵包含 $n$ 个结点的无向树 $T = (V, E)$ 。求最小的顶点子集 $S \subseteq V$ ，使得对于树中的每一条边 $(u, v) \in E$ ，都满足 $u \in S$ 或 $v \in S$ （即树的最小顶点覆盖），输出 $|S|$ 的最小值。

暴力解法

思路

树中共有 $n$ 个结点，每个结点有“选（放士兵）”和“不选（不放士兵）”两种状态。我们可以用 DFS 递归枚举全部 $2^n$ 种点集选择方案。

对于每一种选点方案，遍历树上的每条边 $(u, v)$ ，检查是否至少有一个端点被选入集合。如果所有边均被覆盖，则统计当前集合中点的数量并更新全局最小值。

由于暴力的状态空间为 $O(2^n)$ ，检查边集需要 $O(n)$ ，该方法仅适用于极小规模的数据（如 $n \le 20$ ）。

代码

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/**
 * 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-23 23:26
 * update_at: 2026-10-23 23:26
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 复杂度为 O(2^n * m) = O(2^n * n)，通过指数级枚举所有结点的选/不选状态，
// 逐条检查树上的每条边是否至少有一个端点被选（即被士兵瞭望到），
// 只能用于验证极小规模数据（如 n <= 20）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxn = 30;

ll n;
struct Edge {
    ll u, v;
};
vector<Edge> edges;
ll b[maxn]; // 记录每个结点是否选士兵：1 选，0 不选
ll ans = 1e9;

// 递归枚举每个结点的选择状态
void dfs(ll dep) {
    if (dep == n) {
        // 检查所有边是否都被覆盖
        bool ok = true;
        for (const auto &e : edges) {
            if (!b[e.u] && !b[e.v]) {
                ok = false;
                break;
            }
        }
        if (ok) {
            ll cnt = 0;
            for (ll i = 0; i < n; ++i) {
                if (b[i]) cnt++;
            }
            ans = min(ans, cnt);
        }
        return;
    }

    // 不选当前结点
    b[dep] = 0;
    dfs(dep + 1);

    // 选当前结点
    b[dep] = 1;
    dfs(dep + 1);
}

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

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

    for (ll i = 0; i < n; ++i) {
        ll u, k;
        cin >> u >> k;
        for (ll j = 0; j < k; ++j) {
            ll v;
            cin >> v;
            edges.push_back({u, v});
        }
    }

    ans = n;
    dfs(0);

    cout << ans << "\n";

    return 0;
}

复杂度

时间复杂度： $O(2^n \cdot n)$ 。每个结点 $2$ 种选择，每种状态需线性检查 $n-1$ 条边。
空间复杂度： $O(n)$ 。用于递归调用栈与边集存储。

瓶颈

暴力解法对整棵树进行了全局盲目搜索，完全忽略了树结构的层次特征与无后效性。在树中，一个子树内部的边覆盖方案仅与该子树的根节点是否被选有关，各子树之间互不干扰。盲目枚举所有结点的状态导致了大量的重复计算。

正解

思路

本题是经典的树上最小顶点覆盖问题，可以通过树形动态规划（Tree DP）在 $O(n)$ 线性时间内求解。

任选一个结点作为根（例如结点 $0$ ），将无根树转化为有根树。对于树上的任意一条父子边 $(u, v)$ （ $u$ 为父节点， $v$ 为子节点），边 $(u, v)$ 必须被覆盖，因此 $u$ 与 $v$ 中至少有一个结点需要放置士兵。

定义状态：

$dp[u][0]$ ：表示在以 $u$ 为根的子树中，且结点 $u$ 不放置士兵时，覆盖该子树内部所有边所需的最小士兵数。
$dp[u][1]$ ：表示在以 $u$ 为根的子树中，且结点 $u$ 放置士兵时，覆盖该子树内部所有边所需的最小士兵数。

考虑状态转移：

若 $u$ 不放置士兵（计算 $dp[u][0]$ ）：自身花费为 $0$ 。为使连接父子结点的边 $(u, v)$ 能够被瞭望到，其每一个子结点 $v$ 都必须放置士兵。因此：
$dp[u][0] = \sum_{v \in children(u)} dp[v][1]$
若 $u$ 放置士兵（计算 $dp[u][1]$ ）：自身花费为 $1$ 。此时边 $(u, v)$ 已经被 $u$ 处的士兵覆盖，子结点 $v$ 处放不放士兵均可。为了让总花费最小，子结点 $v$ 应当选择花费更小的状态。因此：
$dp[u][1] = 1 + \sum_{v \in children(u)} \min(dp[v][0], dp[v][1])$

边界与实现细节：

当 $u$ 为叶子结点时， $children(u) = \emptyset$ ，自然有 $dp[u][0] = 0, dp[u][1] = 1$ 。
输入数据每条边只出现一次且未指明父子顺序，建图时需建立无向双向边，通过 DFS 传入父结点参数 fa 避免反向走回。
最终整棵树的最小士兵数为 $\min(dp[0][0], dp[0][1])$ 。

代码

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/**
 * 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-23 23:26
 * update_at: 2026-10-23 23:26
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxn = 1505;

ll n;
vector<ll> e[maxn];
ll dp[maxn][2];
bool vis[maxn];

// 树形 DP
// u: 当前节点，fa: 父节点
void dfs(ll u, ll fa) {
    dp[u][0] = 0; // u 不放士兵
    dp[u][1] = 1; // u 放士兵，花费为 1

    for (ll v : e[u]) {
        if (v == fa) continue;
        dfs(v, u);
        // 如果 u 不放士兵，则其子节点 v 必须放士兵，否则边 (u, v) 无法被瞭望
        dp[u][0] += dp[v][1];
        // 如果 u 放士兵，则子节点 v 可放可不放，取二者最小值
        dp[u][1] += min(dp[v][0], dp[v][1]);
    }
}

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

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

    for (ll i = 0; i < n; ++i) {
        ll u, k;
        cin >> u >> k;
        for (ll j = 0; j < k; ++j) {
            ll v;
            cin >> v;
            e[u].push_back(v);
            e[v].push_back(u);
        }
    }

    // 任选 0 作为根节点进行树形 DP
    dfs(0, -1);

    cout << min(dp[0][0], dp[0][1]) << "\n";

    return 0;
}

复杂度

时间复杂度： $O(n)$ 。建图耗时 $O(n)$ ；DFS 遍历过程中，每个结点访问一次，每条边访问两次，每个结点状态转移的耗时与其度数成正比，总转移耗时为 $\sum O(deg(u)) = O(n)$ 。
空间复杂度： $O(n)$ 。邻接表存储 $2(n-1)$ 条边占用 $O(n)$ 空间，DP 数组及递归栈深度均为 $O(n)$ 。

总结

本题是树形 DP 入门经典题（树的最小顶点覆盖）。核心突破口在于抓住树上每条边的覆盖约束：一条边的两端点至少选其一。通过把无根树定根，将全局约束转化为父子关系约束，利用子树间相互独立的特性设立选与不选两种状态，自底向上合并子树最优解，从而在线性复杂度内解决问题。