「一本通 5.2 例 5」皇宫看守

形式化题目

给定一棵 $n$ 个结点的有根树，每个结点 $i$ 有一个正整数权值 $c_i$ （在该宫殿安置看守的费用）。

要求选出结点的一个子集 $S$ ，使得对每个结点 $u$ ，至少满足下列之一：

$u \in S$ ；
$u$ 的父亲 $\in S$ ；
$u$ 的某个儿子 $\in S$ 。

也就是每个结点要么自己设看守，要么与一个设了看守的相邻结点（父亲或儿子）相连。求 $\sum_{u \in S} c_u$ 的最小值，即树的最小权支配集。

样例说明

输入给出的树结构如下，结点编号与安置费用为 $1:30,\ 2:16,\ 3:5,\ 4:4,\ 5:11,\ 6:5$ ：

graph TD
    1((1, 30)) --- 2((2, 16))
    1 --- 3((3, 5))
    1 --- 4((4, 4))
    2 --- 5((5, 11))
    2 --- 6((6, 5))

在结点 $2, 3, 4$ 上设看守，总费用 $16 + 5 + 4 = 25$ 。此时：结点 $1$ 被儿子 $2,3,4$ 看到，结点 $2$ 自己被选中，结点 $5,6$ 被父亲 $2$ 看到，结点 $3,4$ 自己被选中，整棵树都被覆盖。

若改成只选结点 $1$ ，费用为 $30$ ，更贵；只选 $2,3,4$ 中任意两个则无法覆盖全部结点。所以最少经费为 $25$ ，与样例输出一致。

正解

思路

1. 朴素做法与瓶颈

最直接的做法是枚举每个结点设不设看守，共 $2^n$ 种方案，逐个检查覆盖性并取最小费用，复杂度 $O(2^n \cdot n)$ 。当 $n$ 达到 $1500$ 时完全不可行。

观察覆盖条件：一个结点 $u$ 是否被覆盖，只取决于 $u$ 自己、它的父亲、它的儿子 —— 全是父子两级以内的局部信息。这正是树形 DP 的适用信号：以 $u$ 为根的子树内部如何安排，只受" $u$ 的覆盖由谁负责"这一个信息影响，与子树外无关。

2. 为什么两个状态不够

如果只设" $u$ 是否已被覆盖"的 $0/1$ 两态，会丢掉关键区别：

$u$ 已被儿子看到，子树已经付过钱了；
$u$ 还没被覆盖，只是等着父亲来看它，这笔钱要留到父亲那一层再付。

这两种情况都表现为" $u$ 当前未设看守"，但允许儿子采取的取值不同，代价也不同。因此必须显式区分"指望父亲"，把状态拆成三个。

3. 状态定义

对以 $u$ 为根的子树：

$dp_0[u]$ ： $u$ 自己设看守，子树内所有结点都被看守的最小费用；
$dp_1[u]$ ： $u$ 不设看守，但已被某个儿子看到，子树内所有结点都被看守的最小费用；
$dp_2[u]$ ： $u$ 不设看守，儿子也没看到它， $u$ 只能指望父亲来看它；此时子树内除 $u$ 以外的所有结点必须已被看守的最小费用。

三种状态互斥且穷尽： $u$ 的覆盖来源只有"自己 / 儿子 / 父亲"三种。

4. 状态转移

设 $u$ 的儿子集合为 $sons(u)$ 。

① $dp_0[u]$ ： $u$ 已设看守。 此时每个儿子 $v$ 已被 $u$ 看到，需要自己解决的是 $v$ 的子树内部，且 $v$ 不再有"指望父亲"的必要（父亲已经看到了），三态都合法，取最小值：

dp_0[u] = c_u + \sum_{v \in sons(u)} \min\bigl(dp_0[v],\ dp_1[v],\ dp_2[v]\bigr)

② $dp_2[u]$ ： $u$ 不设看守。 每个儿子 $v$ 都不能再指望 $u$ 来看它，所以 $dp_2[v]$ 不合法，只能在" $v$ 自己设"和" $v$ 被它的儿子看到"之间选：

dp_2[u] = \sum_{v \in sons(u)} \min\bigl(dp_0[v],\ dp_1[v]\bigr)

③ $dp_1[u]$ ： $u$ 不设看守，且被至少一个儿子看到。 在 $dp_2[u]$ 的基础上，只要保证至少有一个儿子取 $dp_0$ 而不是 $\min(dp_0, dp_1)$ 即可。设把儿子 $v$ 从 $\min(dp_0[v], dp_1[v])$ 抬到 $dp_0[v]$ 的增量为

\Delta_v = dp_0[v] - \min\bigl(dp_0[v],\ dp_1[v]\bigr) \geqslant 0

只需挑增量最小的那个儿子承担这个"设看守"的职责：

dp_1[u] = dp_2[u] + \min_{v \in sons(u)} \Delta_v

叶子没有儿子，无法被子结点看到，故 $dp_1[\text{leaf}] = +\infty$ （不可达）。

5. 小规模转移演示

对样例中结点 $2$ （费用 $16$ ，儿子 $5$ 费用 $11$ 、 $6$ 费用 $5$ ，二者都是叶子）演示一次自底向上的完整转移：

结点	角色	$dp_0$	$dp_1$	$dp_2$	说明
5	叶子	11	$+\infty$	0	无儿子， $dp_1$ 不可达
6	叶子	5	$+\infty$	0	同上
2	内部	$16 + \min(11,\infty,0) + \min(5,\infty,0) = 16$	$0 + 5 = 5$	$0 + 0 = 0$	$\Delta_5 = 11,\ \Delta_6 = 5$ ，取小的

表格中 $dp_0$ 是"自己出钱并替儿子兜底"， $dp_2$ 是"自己不出钱、把责任推给父亲"，因此叶子的 $dp_2 = 0$ 。结点 $2$ 的 $dp_1 = 5$ 表示"不选 $2$ 、改选儿子 $6$ 来看守 $2$ "只需 $5$ 元，比对结点 $5$ 做同样的事（ $11$ 元）便宜，所以 $dp_1$ 选中的增量来自 $\Delta_6$ 。这正是 $dp_1$ 转移中"挑增量最小的儿子"的具体体现。

6. 答案与实现

根结点没有父亲， $dp_2[\text{root}]$ 不合法，因此整棵树的答案是

\min\bigl(dp_0[\text{root}],\ dp_1[\text{root}]\bigr)

转移必须自底向上进行。这里不用递归（链状树会爆栈）：输入本身给的就是"父亲 → 儿子"的有向描述，入度为 $0$ 的结点即为根；从根开始用栈收集自顶向下的访问序，把它逆序即为自底向上的转移序，直接迭代即可。

代码

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#!/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-09-30 20:09
# update_at: 2026-09-30 20:09

import sys

INF = 1 << 60  # 比任何合法经费和大得多，用来表示"这个状态不成立"


def min_guard_cost(n: int, cost: list[int], children: list[list[int]], root: int) -> int:
    """求树上最小权支配集的权值和：每个点要么自己设看守，要么被父亲或儿子看到。

    dp0[u]：u 自己设看守，u 子树全部被看守的最小花费。
    dp1[u]：u 不设看守，但 u 已被它的某个儿子看到，u 子树全部被看守的最小花费。
    dp2[u]：u 不设看守、也没有任何儿子看到 u，此时 u 只能指望父亲来看它，
            子树内（除 u 自己）必须已经全部被看守的最小花费。
    三者互斥且覆盖全部情况，故答案就是根节点上 min(dp0, dp1)（根没有父亲）。
    """
    # 输入已经是有根树的父子关系，按读入顺序展开即得到自顶向下的遍历序，
    # 逆序就是自底向上的转移序，不需要显式 DFS。
    order: list[int] = []
    stack = [root]
    while stack:
        u = stack.pop()
        order.append(u)
        stack += children[u]

    dp0 = [0] * (n + 1)
    dp1 = [0] * (n + 1)
    dp2 = [0] * (n + 1)

    for u in reversed(order):
        dp0[u] = cost[u] + sum(min(dp0[v], dp1[v], dp2[v]) for v in children[u])
        # u 不设看守时，每个儿子 v 都不能指望 u 来看它，所以只能取 dp0[v] / dp1[v]。
        dp2[u] = sum(min(dp0[v], dp1[v]) for v in children[u])
        # 至少有一个儿子设了看守才能让 u 被看到：把其中一个儿子的 dp2 换成 dp0，
        # 代价增量最小的那次替换就是最优选择。
        extra = min(
            (dp0[v] - min(dp0[v], dp1[v]) for v in children[u]),
            default=INF,  # 叶子没有儿子，dp1 不可能成立
        )
        dp1[u] = dp2[u] + extra

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


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    cost = [0] * (n + 1)
    children: list[list[int]] = [[] for _ in range(n + 1)]
    has_parent = [False] * (n + 1)

    for _ in range(n):
        u, k, m = next(data), next(data), next(data)  # 结点标号、经费、儿子数
        cost[u] = k
        children[u] = [next(data) for _ in range(m)]
        for v in children[u]:
            has_parent[v] = True

    # 题面给出的是"父亲 → 儿子"的有向描述，入度为 0 的结点就是皇宫的起点（根）。
    root = next(u for u in range(1, n + 1) if not has_parent[u])
    print(min_guard_cost(n, cost, children, root))


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
95
96
97
98
99
100
101
102
103
104/**
 * 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
 */
// 树的最小权支配集：三态树形 DP。
// dp0[u]：u 自己设看守，u 子树全部被看守的最小经费；
// dp1[u]：u 不设看守，但被某个儿子看到，u 子树全部被看守的最小经费；
// dp2[u]：u 不设看守、儿子也没看到它，只能指望父亲，u 子树内除 u 外
//         全部被看守的最小经费。
// 根没有父亲，答案为 min(dp0[root], dp1[root])。

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

typedef long long ll;

const int MAXN = 1505;
const ll INF = 1e18;

ll n;
ll cost[MAXN]; // cost[u]：在 u 宫殿设看守的经费
int child_cnt[MAXN]; // child_cnt[u]：u 的儿子数
int child[MAXN][MAXN]; // child[u][j]：u 的第 j 个儿子（题面即按此给出，直接存矩阵）
bool has_parent[MAXN]; // has_parent[v]：v 是否出现过在某个父亲的儿子列表里
int order[MAXN]; // order：自顶向下的访问序，逆序即自底向上的转移序

ll dp0[MAXN], dp1[MAXN], dp2[MAXN];

// 从根出发用栈收集自顶向下遍历序；输入本身就是"父亲 -> 儿子"的有向描述，
// 入度为 0 的结点即根。
int find_root() {
    for (int u = 1; u <= n; u++) {
        if (!has_parent[u]) return u;
    }
    return 1; // 理论上不会走到这里
}

// 自底向上做三态转移。
void solve() {
    int root = find_root();

    // 用数组模拟栈：先得到自顶向下的访问序 order[0..cnt-1]。
    int cnt = 0;
    order[cnt++] = root;
    for (int i = 0; i < cnt; i++) {
        int u = order[i];
        for (int j = 1; j <= child_cnt[u]; j++) {
            order[cnt++] = child[u][j];
        }
    }

    // 逆序迭代：处理 u 时它的所有儿子已经转移完毕。
    for (int i = cnt - 1; i >= 0; i--) {
        int u = order[i];

        // dp0：u 自己设看守，每个儿子三态任选（父亲已看到它，dp2 也合法）。
        // dp2：u 不设看守，每个儿子都不能指望 u，只能取 dp0 / dp1。
        ll sum0 = cost[u], sum2 = 0;
        // min_delta：把某个儿子从 min(dp0,dp1) 抬到 dp0 的最小代价增量，
        // 用于计算"至少一个儿子设了看守"的 dp1。
        ll min_delta = INF;
        for (int j = 1; j <= child_cnt[u]; j++) {
            int v = child[u][j];
            sum0 += min(min(dp0[v], dp1[v]), dp2[v]);
            sum2 += min(dp0[v], dp1[v]);
            ll delta = dp0[v] - min(dp0[v], dp1[v]);
            if (delta < min_delta) min_delta = delta;
        }
        dp0[u] = sum0;
        dp2[u] = sum2;
        if (child_cnt[u] == 0) {
            dp1[u] = INF; // 叶子没有儿子，不可能"被儿子看到"
        } else {
            dp1[u] = sum2 + min_delta;
        }
    }

    cout << min(dp0[root], dp1[root]) << endl;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u, m;
        ll k;
        cin >> u >> k >> m;
        cost[u] = k;
        child_cnt[u] = m;
        for (int j = 1; j <= m; j++) {
            cin >> child[u][j];
            has_parent[child[u][j]] = true;
        }
    }

    solve();

    return 0;
}

复杂度

时间复杂度： $O(n)$ 。每个结点在自底向上的过程中只被转移一次，内部对儿子的三次求和合计只遍历该结点的每条父子边常数次。
空间复杂度： $O(n)$ 。cost、children 邻接表、三个 DP 数组以及遍历序 order 均为 $O(n)$ 。

总结

模型转化：把"看守所有宫殿"翻译成树上的最小权支配集 —— 每个点必须被自己或相邻的父亲/儿子覆盖，目标是最小化选中点的权值和。
状态设计的动机：一个点"已覆盖"与"未覆盖但等父亲"的代价不同，二态会丢失信息；按覆盖来源（自己 / 儿子 / 父亲）拆成 $dp_0/dp_1/dp_2$ 三态后，子树之间才互相独立。
转移的关键技巧： $dp_1$ 用"在 $dp_2$ 基础上挑增量最小的儿子改成必选"来表达"至少一个儿子设看守"这一约束，避免了对子集再枚举。答案取 $\min(dp_0[\text{root}], dp_1[\text{root}])$ 。
实现注意：树形 DP 依赖自底向上序，用显式栈 + 逆序迭代替代深度递归，既避免爆栈又保持 $O(n)$ 。