树上支配集

1 题意

例题:luogu P2458: 保安站岗。

在树的节点上安排保安。选择节点 uu 需要费用 cuc_u,可以看守 uu 及其所有相邻节点。要求每个节点都被看守,求最小总费用。

一个点集若能使每个节点自身被选,或者与某个被选节点相邻,就称为支配集。本题求树上的最小权支配集;若所有费用均为 11,就是求最少选择多少个节点。

原题中 1≤n≤15001\le n\le1500、1≤cu≤100001\le c_u\le10000,节点从 11 编号。

在 战略游戏 中要求覆盖每条边;本题要求覆盖每个点。例如链 1−2−3−41-2-3-4,只选 1,41,4 已经覆盖全部节点,但边 (2,3)(2,3) 的两端都没选。两种限制不能混用。

2 三种状态

前两篇只需区分子树根选或不选。本题中,根不选还要细分:已经被孩子覆盖,还是需要父节点来覆盖。 两者对父节点的要求不同,不能合并。

记 TuT_u 为以 uu 为根的子树。三个状态都要求 TuT_u 中除 uu 之外的节点已经得到覆盖:

状态 uu 的情况 对父节点的要求
f[u][0]f[u][0] 不选 uu,至少一个孩子被选,uu 已被覆盖 无
f[u][1]f[u][1] 选择 uu 无
f[u][2]f[u][2] 不选 uu,也没有孩子被选,uu 尚未被覆盖 父节点必须选择

每个状态保存满足这些条件的最小费用。状态 22 是允许暂时留下的一项需求,并不表示整棵树可以存在未覆盖节点。

3 转移方程

设 C(u)C(u) 为 uu 的孩子集合。

3.1 选择 u

选择 uu 后,等待父亲覆盖的孩子可以得到覆盖,其余两种状态也合法:

f[u][1]=cu+∑v∈C(u)min⁡(f[v][0],f[v][1],f[v][2]). f[u][1]=c_u+\sum_{v\in C(u)}\min\bigl(f[v][0],f[v][1],f[v][2]\bigr).

3.2 等待父亲

要让 uu 保持未被覆盖,就不能选择任何孩子;而 uu 自己没选,也不能接纳等待它覆盖的孩子。因此,每个孩子只能处于状态 00:

f[u][2]=∑v∈C(u)f[v][0]. f[u][2]=\sum_{v\in C(u)}f[v][0].

3.3 被孩子覆盖

此时 uu 不选,每个孩子只能取状态 00 或 11,并且至少一个孩子必须取状态 11。

先不管“至少一个”的限制,记:

bv=min⁡(f[v][0],f[v][1]),B=∑v∈C(u)bv. b_v=\min(f[v][0],f[v][1]),\qquad B=\sum_{v\in C(u)}b_v.

如果强制孩子 vv 被选,需要把它的贡献从 bvb_v 换成 f[v][1]f[v][1],补上 f[v][1]−bvf[v][1]-b_v。选择补差最小的孩子即可:

f[u][0]=B+min⁡v∈C(u)(f[v][1]−bv). f[u][0]=B+\min_{v\in C(u)}\bigl(f[v][1]-b_v\bigr).

如果原来的最优选择已经包含某个孩子的状态 11,最小补差就是 00,不会多付费用。若状态 00 与 11 费用相同,也可以免费改选状态 11。

这个式子只保证至少选一个孩子,允许其他孩子也被选。不能改成“恰好选择一个孩子”。

4 初值与答案

对于叶子 uu:

f[u][0]=+∞,f[u][1]=cu,f[u][2]=0. f[u][0]=+\infty,\qquad f[u][1]=c_u,\qquad f[u][2]=0.

叶子没有孩子,不能被孩子覆盖;自己选择需要支付费用;等待父亲时暂时不花钱。代码用 INF 表示不可行,并将不可行费用的累加截断到 INF,避免连续相加溢出。

根没有父亲,答案只能是:

min⁡(f[root][0],f[root][1]). \min(f[root][0],f[root][1]).

特别地,只有一个节点时,必须选择它,答案为它的费用。若把根的状态 22 也取入答案,就会错误地得到 00。

5 手算示例

下面是自拟示例。节点外标注费用,实心节点表示选择。选择 3,43,4,总费用为 44:33 覆盖根 11,44 覆盖节点 22。

树的边为 1-2、1-3、2-4,费用依次为 10、2、3、1,选择节点 3 和 4,费用为 4

节点 被孩子覆盖 f[u][0]f[u][0] 自己选择 f[u][1]f[u][1] 等待父亲 f[u][2]f[u][2]
4 +∞+\infty 1 0
2 1 2 +∞+\infty
3 +∞+\infty 3 0
1 4 11 +∞+\infty

根不选时,孩子 22 的最优费用是 11,孩子 33 的最优费用是 33。后者已经被选,所以补差为 00,得到 f[1][0]=1+3=4f[1][0]=1+3=4。

6 正确性

固定 uu 的状态后,孩子允许的状态由覆盖关系确定。状态 11 和 22 中,各棵孩子子树独立取最小值即可。

状态 00 中,每个合法方案都至少选择一个孩子 vv,因此费用不少于 B+f[v][1]−bvB+f[v][1]-b_v,进而不少于最小补差公式。反过来,强制补差最小的孩子选择,其余孩子各取最优状态,就能构造出达到公式值的合法方案。

从叶子向上归纳,每个状态都是其条件下的最小费用。根排除状态 22 后,全树所有节点均被覆盖。

7 代码实现

P2458 每行依次给出 节点编号 费用 孩子数 孩子列表,已明确父子关系。只保存向孩子的边,找到没有父节点的根。

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

const int maxn = 1500 + 5;
const ll INF = 1LL << 60;

vector<int> g[maxn];
int cost[maxn];
bool has_parent[maxn];
ll f[maxn][3];

void dfs(int u) {
    f[u][1] = cost[u];  // 选择 u
    f[u][2] = 0;        // u 未被子树覆盖,等待父亲选择
    ll base = 0, extra = INF;

    for (int v : g[u]) {
        dfs(v);
        // u 选择后,可以接纳孩子的全部三种状态。
        f[u][1] += min({f[v][0], f[v][1], f[v][2]});
        // u 必须尚未被覆盖,因此孩子不能选,也不能等待 u。
        f[u][2] = min(INF, f[u][2] + f[v][0]);

        ll best = min(f[v][0], f[v][1]);
        base += best;  // u 不选,孩子必须在自己的子树内得到覆盖
        extra = min(extra, f[v][1] - best);  // 强制一个孩子选择的最小补差
    }
    // 没有孩子时,无法通过孩子覆盖 u。
    f[u][0] = (extra == INF ? INF : base + extra);
}

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int u, k;
        cin >> u >> k;
        cost[u] = k;
        int children;
        cin >> children;
        while (children--) {
            int v;
            cin >> v;
            g[u].push_back(v);  // P2458 已给出父亲到孩子的方向
            has_parent[v] = true;
        }
    }

    int root = 1;
    while (has_parent[root]) ++root;
    dfs(root);
    // 根没有父亲,不能接受等待父亲覆盖的状态 2。
    cout << min(f[root][0], f[root][1]) << '\n';
    return 0;
}

每个节点只计算三个状态,每条父子边合并一次,时间复杂度为 O(n)O(n),空间复杂度为 O(n)O(n)。原题有限费用不超过 1500×100001500\times10000;代码使用 long long 为不可行标记及累加留出空间。

8 相关题解

暂无相关题解