[JSOI2018] 潜入行动

题意

给一棵树，要恰好在 k 个点上放监听设备。

如果在点 u 放设备，那么它只能监听 u 的相邻点，不能监听 u 自己。

要求整棵树上每个点都至少被某个相邻点上的设备监听，问合法方案数。

答案对 10^9+7 取模。

思路

先看一个可以直接验证想法的朴素解：

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 25;

int n, k;
vector<int> g[MAXN];

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

    // brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
    // 枚举所有大小恰好为 k 的点集，检查每个点是否都有相邻点被选中。
    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int answer = 0;
    int total_mask = 1 << n;

    for (int mask = 0; mask < total_mask; mask++) {
        if (__builtin_popcount((unsigned) mask) != k) {
            continue;
        }

        bool ok = true;
        for (int u = 1; u <= n; u++) {
            bool covered = false;
            for (size_t i = 0; i < g[u].size(); i++) {
                int v = g[u][i];
                if (mask & (1 << (v - 1))) {
                    covered = true;
                    break;
                }
            }
            if (!covered) {
                ok = false;
                break;
            }
        }

        if (ok) {
            answer++;
        }
    }

    cout << answer << '\n';
    return 0;
}

这就是树上的“总支配集”计数问题。
由于要求恰好选 k 个点，显然要做树上背包。

关键在状态设计。

设：

f[u][j][sel][cov]

表示在 u 的子树里一共放了 j 个设备时：

sel=0/1：u 自己是否放设备
cov=0/1：u 是否已经被某个儿子监听

为什么只记录“是否被儿子监听”？
因为 u 还能不能被父亲监听，要等合并到父亲时再判断。

初始时：

f[u][0][0][0] = 1
f[u][1][1][0] = 1

合并儿子 v 时，只有一种额外约束：

v 这个点必须已经被监听，或者它可以被父亲 u 监听。

也就是条件：

cov_v || sel_u

同时，u 是否被儿子监听，要看是否存在某个儿子放了设备，所以新状态里的 cov_u 要和 sel_v 做或运算。

最后根节点没有父亲，所以它不能指望父亲来监听。
因此最终答案只能是：

f[root][k][0][1]
f[root][k][1][1]

这两种状态之和。

DP 转移方程

核心状态：

f[u][j][sel][cov]

核心转移：

合并儿子要求 cov_v || sel_u，新 cov_u |= sel_v

答案收束：

f[root][k][0][1]+f[root][k][1][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
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int MAXK = 105;
const int MOD = 1000000007;

int n, k;
vector<int> g[MAXN];
int parent_node[MAXN];
int order_arr[MAXN];
int order_cnt;
int subtree_size[MAXN];
int f[MAXN][MAXK][2][2];
int tmp[MAXK][2][2];

void add_mod(int &x, long long y) {
    x = (x + y) % MOD;
}

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

    cin >> n >> k;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<int> st;
    st.push_back(1);
    parent_node[1] = 0;

    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        order_arr[++order_cnt] = u;
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (v == parent_node[u]) {
                continue;
            }
            parent_node[v] = u;
            st.push_back(v);
        }
    }

    for (int idx = order_cnt; idx >= 1; idx--) {
        int u = order_arr[idx];

        subtree_size[u] = 1;
        f[u][0][0][0] = 1;
        if (k >= 1) {
            f[u][1][1][0] = 1;
        }

        for (size_t e = 0; e < g[u].size(); e++) {
            int v = g[u][e];
            if (v == parent_node[u]) {
                continue;
            }

            int limit_u = min(subtree_size[u], k);
            int limit_v = min(subtree_size[v], k);
            int limit_all = min(subtree_size[u] + subtree_size[v], k);

            for (int i = 0; i <= limit_all; i++) {
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        tmp[i][a][b] = 0;
                    }
                }
            }

            for (int i = 0; i <= limit_u; i++) {
                for (int j = 0; j <= limit_v && i + j <= k; j++) {
                    for (int sel_u = 0; sel_u < 2; sel_u++) {
                        for (int cov_u = 0; cov_u < 2; cov_u++) {
                            int ways_u = f[u][i][sel_u][cov_u];
                            if (ways_u == 0) {
                                continue;
                            }
                            for (int sel_v = 0; sel_v < 2; sel_v++) {
                                for (int cov_v = 0; cov_v < 2; cov_v++) {
                                    int ways_v = f[v][j][sel_v][cov_v];
                                    if (ways_v == 0) {
                                        continue;
                                    }

                                    if ((cov_v | sel_u) == 0) {
                                        continue;
                                    }

                                    add_mod(
                                        tmp[i + j][sel_u][cov_u | sel_v],
                                        1LL * ways_u * ways_v
                                    );
                                }
                            }
                        }
                    }
                }
            }

            subtree_size[u] += subtree_size[v];
            if (subtree_size[u] > k) {
                subtree_size[u] = k;
            }

            for (int i = 0; i <= subtree_size[u]; i++) {
                for (int a = 0; a < 2; a++) {
                    for (int b = 0; b < 2; b++) {
                        f[u][i][a][b] = tmp[i][a][b];
                    }
                }
            }
        }
    }

    int answer = f[1][k][0][1];
    add_mod(answer, f[1][k][1][1]);
    cout << answer << '\n';
    return 0;
}

复杂度

时间复杂度 $O(nk^2)$ ，空间复杂度 $O(nk)$ 。

这里 k <= 100，可以通过。

总结

这题最关键的是看清：

一个点是否放设备
一个点是否已经被儿子覆盖

只要这两个状态定清楚，合并儿子的条件就是一句：

cov_v || sel_u

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。