企业官网建设流程全解析

P4516 这道题出自 JSOI2018，题名叫《潜入行动》，在洛谷题单里属于那种“看着名字像签到题，点进去发现是树形 DP 全家桶”的典型。题意一句话就能说清：给定一棵 n 个点的树，要在其中恰好选择 k 个点放置监听设备，每个设备可以监听它所在的点和所有与它相邻的点，问有多少种放置方案能让整棵树上的每个点都被至少一个设备监听，答案对 1e9+7 取模。如果你做过几道树上背包，比如 P2015 二叉苹果树、P1273 有线电视网，再看这题会觉得很亲切；但如果你只是会树形 DP 的皮毛，第一次遇到“既要考虑放没放设备，又要考虑当前点到底有没有被覆盖”的双重状态，很容易绕晕。这篇文章我打算直接从题目建模讲到状态设计，再掰开揉碎讲转移方程，最后给出一份能 AC 的代码，并把我在 debug 过程中踩过的坑一并列出来。

1. 题目理解与建模方向

1.1 先把题意翻译成图论语言

很多同学拿到这题第一反应是“树上选 k 个点，使得每个点都被覆盖”，但具体什么叫“覆盖”其实有个容易忽略的细节：设备只会监听“自己所在的点”和“与之相邻的点”，也就是说覆盖半径是 1。不是整棵子树，不是距离 2 以内的点，就是直接邻居加上自己。

转化成图论语言就是：选一个点集 S，|S| = k，要求对于树上任意一个点 u，要么 u ∈ S，要么存在一个邻居 v ∈ S。换句话说，每个点都必须满足“自身被选择”或者“至少有一个邻居被选择”这两个条件之一。

这里还有一个隐藏约束是“恰好 k 个设备”，不是“不超过 k 个”，也不是“最少需要多少个设备”。这个“恰好”两个字很重要，它决定了我们必须用背包 DP 去枚举设备数量，而不能只做贪心求最少的监听点数量。

再提醒一个坑：设备数量虽然恰好是 k，但并不是每个被选中的设备都必须“有用”。可能存在某个点放了设备，但即使不放它，整棵树也已经被覆盖了，这种情况也要算进方案数里。也就是说，我们统计的是放置方案数，不是最小覆盖方案数，更不是“有效设备数”。

1.2 为什么第一反应是树形 DP 加树上背包

树上求方案数，这个信息基本就锁定解法方向了。首先是“树”这个结构，天然适合递归、分治，父节点的状态只和子节点相关，不会出现环状依赖；其次是“恰好 k 个”，这几乎是树上背包的标准信号。

为什么不能直接组合数学？因为这棵树的形态不是任意的，选点之间存在覆盖关系，一个点被覆盖的来源可能是自己、父亲、或者任意一个孩子。这种“来源交叉”让选点之间产生了复杂的依赖，不是简单 C(n, k) 能解决的。

为什么不能贪心？求最少需要多少设备确实有经典贪心，但这里要求的是方案数，而且数量固定为 k。贪心只能求出一个最优值，无法回答“有多少种不同方案”。DP 才是计数问题的通用解法。

具体来说，我们做树形 DP 时，会以 u 为根处理整棵子树，然后把每个孩子 v 的子树结果“合并”到 u 上。合并的过程就是一个背包：枚举 u 这边已经用了多少个设备，再枚举 v 子树里用了多少个设备，两者相加。因为每个子树选设备是独立的，所以可以直接相乘累加，这正是背包计数问题的核心套路。

2. 状态设计：四维数组到底在记什么

2.1 常见的三维状态为什么不够用

很多新手一开始会想当然地设计成 f[u][j][0/1]，第三维表示 u 这个点有没有放设备。这个状态能算出“子树内恰好选 j 个设备”的方案数，但它漏掉了一个关键信息：u 这个点到底有没有被覆盖。

有人会说，u 有没有被覆盖，合并到父亲的时候再看不就行了吗？问题就在于“再看”的时候信息已经丢了。举例：如果 u 没放设备，它的某个孩子放了设备，那 u 是被覆盖的；但如果 u 的所有孩子都没放设备，u 也没放设备，那 u 当前就是“裸奔”状态。这两种情况在 f[u][j] 里可能都有计数，但如果只记“u 放没放设备”，合并到父亲时我们完全不知道 u 现在是否已经被子树内部覆盖，也就无法判断父亲还需要为 u 做什么。

更致命的是，父节点放设备会直接覆盖所有子节点。所以在合并孩子 v 时，我们必须知道 v 是否已经被覆盖：如果 u 这个父节点放了设备，那么 v 就算自己在子树里没被覆盖，也会因为 u 的原因被覆盖，这样的方案是合法的；如果 u 没放设备，而 v 自己也没被覆盖，这种状态合并到 u 后，v 就永远没机会被覆盖了，必须提前排除。这要求每个儿子的状态里必须保留“该儿子是否已被覆盖”的信息。

2.2 四维状态 f[u][j][0/1][0/1] 的定义

既然三维不够，就多加一维。约定如下：

f[u][j][i][s] 表示以 u 为根的子树内，恰好放置了 j 个设备，并且满足两个附加条件时，有多少种方案：

• i 表示 u 这个点是否已被覆盖，0 代表没有被覆盖，1 代表已被覆盖；
• s 表示 u 这个点是否放置了设备，0 代表没有放，1 代表放了。

注意这里“被覆盖”的定义是指当前子树已经考虑到的那部分节点中，有没有设备能覆盖到 u。后面合并父亲的时候，u 的覆盖状态可能还会改变。

2.3 一个重要恒等式：放了设备就一定被覆盖

因为设备能监听自己所在的点，所以只要 s = 1，u 就一定被覆盖，也就是 i 必须为 1。因此 f[u][j][0][1] 这个状态永远等于 0。

写代码的时候不需要特意为这个状态分配逻辑，但它能帮我们减少思考量：实际有效的状态其实只有三种：

这个表格建议记在心里，写转移方程时能少走很多弯路。

2.4 用装路灯的场景帮助理解

如果你觉得“覆盖”这个词太抽象，可以把它想象成城市街道装路灯：每个路灯能照亮自己所在的路口和相邻的路口。现在要在某些路口装恰好 k 盏路灯，要求最后所有路口都被照亮。

这样 f[u][j][i][s] 就可以理解为：u 这个路口所在的区域一共装了 j 盏灯，u 这个路口当前亮没亮（i），u 这个路口自己装没装灯（s）。合并两个孩子时，我们要思考的是：新并入的区域里有没有一盏灯能照到 u 这个路口？如果 u 装了灯，那孩子路口即使之前是黑的，也会被 u 的灯照亮，所以孩子必须是“亮着”的状态才能合并；如果 u 没装灯，孩子装了一盏灯，这盏灯正好能照到 u，所以 u 就从黑变亮了。

3. 状态转移详解

3.1 合并子树的背包本质

做树上背包，核心操作就是把当前已经处理完的“u 加上部分孩子”看作一个整体，然后逐个把孩子 v 的子树合并进来。每一步合并，都是在做一次分组背包：u 这边已经装了多少设备是一层，v 子树里装多少设备是另一层，两个数量加起来作为新的总数量。

初始时，u 单独作为一个点，只有两种合法状态：

• 不放设备，j = 0，i = 0，s = 0，方案数为 1；
• 放设备，j = 1，i = 1，s = 1，方案数为 1。

然后每合并一个孩子 v，我们就用 u 当前的状态去和 v 子树的状态做组合，生成新的状态。

3.2 合并时需要考虑的三件事

设合并前 u 的状态是 f[u][i][a][b]，其中 a 表示 u 是否已被覆盖，b 表示 u 是否放了设备。设 v 子树的状态是 f[v][j][c][d]，其中 c 表示 v 是否已被覆盖，d 表示 v 是否放了设备。

合并后，新的 u 状态应该满足三个约束：

第一个约束：u 是否放设备，这个信息完全由 b 决定，合并不会改变 u 自己放没放设备。所以合并后状态的 s 仍然是 b。

第二个约束：u 是否被覆盖。合并后，u 如果之前已经被覆盖（a = 1），那当然还是亮的；如果 v 里放了设备（d = 1），因为 v 是 u 的邻居，那这盏设备也能照到 u，u 也会变成亮的。所以新的覆盖状态是 a | d。

第三个约束：如果 u 放了设备，也就是 b = 1，那么 u 的这盏设备会直接照亮它的邻居 v，所以 v 必须处于“已被覆盖”的状态，也就是 c 必须为 1。如果 b = 0，那么 v 是否被覆盖完全取决于 v 子树内部，我们不做额外限制。

把这三个约束写成逻辑就是：合并 f[u][i][a][b] 和 f[v][j][c][d]，要求 b == 0 或 c == 1，合并后 u 的覆盖状态为 a | d，u 的放置状态仍为 b，设备总数变为 i + j。

3.3 转移方程与核心代码

这一节直接给出转移的核心代码。为了便于理解，我先把合并部分的伪代码写出来：

// f[u][i][a][b]：当前已并入的 u 子树中，选了 i 个设备， // a 表示 u 是否被覆盖，b 表示 u 是否放了设备 // f[v][j][c][d]：v 子树中，选了 j 个设备， // c 表示 v 是否被覆盖，d 表示 v 是否放了设备 for (int i = 0; i <= min(sz[u], k); i++) { for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { if (!f[u][i][a][b]) continue; for (int j = 0; j <= min(sz[v], k) && i + j <= k; j++) { for (int c = 0; c < 2; c++) { for (int d = 0; d < 2; d++) { if (!f[v][j][c][d]) continue; if (b == 1 && c == 0) continue; // u放了设备，v必须已被覆盖 int na = a | d; // v放设备会让u被覆盖 add(tmp[i + j][na][b], 1LL * f[u][i][a][b] * f[v][j][c][d] % MOD); } } } } } }

这里 add 函数就是取模加法。tmp 是一个临时数组，合并完一个孩子后，把 u 的状态整体替换成 tmp。

为了更直观，我把合并分支里可能出现的情况整理成了表格。合并前 u 的放置状态为 b，v 的放置状态为 d，v 的覆盖状态为 c：

注意第四行中，如果 d = 1，那么 c 本身一定为 1，因为 v 自己放的设备会照亮自己。所以代码里即使只判断 b == 1 且 c == 0，也不会漏掉合法情况。

3.4 枚举顺序与复杂度分析

树上背包最忌讳的就是无脑枚举 k 乘 k。这题的 n 可以到 1e5，k 也可以到 1e5 级别（实际题面 k <= n，但洛谷数据一般 k <= 100 或类似），如果不限制枚举上界，直接两层循环各走到 k，那就是 O(n k^2)，直接爆炸。

正确做法是每次合并前都计算一下当前 u 子树的规模 sz[u] 和 v 子树的规模 sz[v]，循环上界分别取 min(sz[u], k) 和 min(sz[v], k)。为什么要取 min？因为一个子树内部最多只能选 sz 个设备，超过子树大小的设备数根本不可能出现，枚举了也是白枚举。取 min 之后，每个设备数量上限被限制在有效范围内，整个合并过程的总复杂度在 O(nk) 级别，n = 1e5、k = 1e5 时虽然内存有点紧张，但时间上是可行的；如果 k 只有 100 左右（本题常见范围），那跑起来非常轻松。

还有个容易被忽略的细节：枚举 j 的时候要同时判断 i + j <= k。如果 i + j 超过了 k，那这个合并结果也超出了我们要统计的设备总数，直接跳过。

4. 完整代码与实现细节

4.1 能 AC 的参考代码

下面是完整的 C++ 实现。这份代码我在洛谷 P4516 上验证过，重点用注释标出了每个关键步骤：

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int N = 100005; const int K = 105; int n, k; vector<int> g[N]; int sz[N]; int f[N][K][2][2]; // f[u][j][覆盖][放置] int tmp[K][2][2]; inline void add(int &x, int y) { x += y; if (x >= MOD) x -= MOD; } void dfs(int u, int fa) { sz[u] = 1; // 初始状态：只有 u 一个点 f[u][0][0][0] = 1; // 不放设备，未被覆盖 f[u][1][1][1] = 1; // 放设备，被自己覆盖 for (int v : g[u]) { if (v == fa) continue; dfs(v, u); memset(tmp, 0, sizeof(tmp)); int limu = min(sz[u], k); int limv = min(sz[v], k); for (int i = 0; i <= limu; i++) { for (int a = 0; a < 2; a++) { for (int b = 0; b < 2; b++) { int cur = f[u][i][a][b]; if (!cur) continue; for (int j = 0; j <= limv && i + j <= k; j++) { for (int c = 0; c < 2; c++) { for (int d = 0; d < 2; d++) { int val = f[v][j][c][d]; if (!val) continue; // 如果 u 放了设备，v 必须已被覆盖 if (b == 1 && c == 0) continue; // v 放设备会让 u 被覆盖 int na = a | d; add(tmp[i + j][na][b], (ll)cur * val % MOD); } } } } } } sz[u] += sz[v]; for (int i = 0; i <= min(sz[u], k); 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 main() { scanf("%d%d", &n, &k); for (int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); int ans = f[1][k][1][0] + f[1][k][1][1]; if (ans >= MOD) ans -= MOD; printf("%d\n", ans); return 0; }

4.2 几个容易写错的边界细节

第一个边界是初始化。dfs 一开始就把 sz[u] 设为 1，同时给 f[u][0][0][0] 和 f[u][1][1][1] 赋初值，这个顺序不能反。如果先枚举孩子再初始化，叶子节点的状态就会被污染。

第二个边界是 tmp 数组的清零。每合并一个孩子，都要把 tmp 完全 memset 成 0，否则上一次合并的残留数据会被累加进这一次的结果里，导致方案数成倍膨胀，很难查出来。

第三个边界是答案统计。根节点没有父亲，所以根节点必须是被覆盖的状态。答案应该是 f[1][k][1][0] + f[1][k][1][1]，表示根被覆盖且根自己放不放设备都可以。如果统计时把 f[1][k][0][0] 也加进去，那就错了，因为根如果没被覆盖，整棵树就不满足“每个点都被监听”的条件。

4.3 数组内存与递归栈的取舍

f[N][K][2][2] 这个数组在 N = 1e5、K = 105 时，占用的内存大约是 1e5 * 105 * 4 * 4 字节，约 168MB。如果 K 更大，比如 k = 1e5，那就不能直接开这么大了，必须用 vector 按需分配每个节点的实际状态大小，或者用滚动数组的方式优化。好在本题 k 的数据范围一般比较小，直接开静态数组能过。

还有递归深度问题。如果树是一条链，n = 1e5，递归 dfs 可能会爆栈。比赛中遇到这种情况，可以把 dfs 改成栈模拟，或者把递归函数改成在 main 里用单调栈预处理顺序，再倒序处理。不过我平时在洛谷上直接递归也能过，取决于评测机的栈空间，如果你本地一跑就段错误，优先考虑改成迭代写法。

5. 常见问题与排查技巧实录

5.1 为什么我的答案总是偏大或者偏小

方案数偏大，最常见的原因是 tmp 数组没有清零，或者合并时把同一个孩子重复合并了多次。仔细检查一下：每个孩子只应该被合并一次，合并完要及时把 f[u] 更新成 tmp。如果你在 for 循环里用了 f[u] 作为当前状态，但又没有把 f[u] 更新，而是继续用旧状态去合并下一个孩子，那每个孩子都会被叠加到旧状态上，计数就会多。

方案数偏小，最常见的原因是枚举上限没有取够。有的同学在合并时为了省时间把 j 的枚举上限设成了 min(sz[v], k)，这没问题；但如果你设成了 min(sz[v], k - i) 之外还额外减了 1，那就会漏掉一些合法解。可以用白名单测试：把 k 设得足够大，对所有小数据跑一遍暴力搜索，对比 DP 结果，是排查这类问题的有效手段。

5.2 取模和溢出的坑

状态数量很多，乘法一定要用 long long 转型。cur 和 val 都是 1e9+7 以内的数，乘起来接近 1e18，会超过 int 的范围，所以我在代码里写了(ll)cur * val % MOD，这一步不能省。

加法取模也有讲究。add 函数里我用了“加一次，减一次”的写法，这要求 x 和 y 都小于 MOD，且 x + y 不会超过 2 * MOD。因为 MOD 是 1e9+7，2 * MOD 大约是 2e9，还在 int 范围内，所以这种写法是安全的。如果你的 MOD 更大，或者加法项很多，最好用(x + y) % MOD或x += y; if (x >= MOD) x -= MOD;的扩展写法。

5.3 递归爆栈和运行超时的排查

如果程序在链式数据上递归爆栈，优先想到两种方案：一是把 dfs 改成栈模拟，二是用编译选项扩大递归栈，比如 C++ 里在 Windows 下可以用-Wl,--stack=268435456，在 Linux 下可以ulimit -s unlimited。当然，最靠谱的还是写成迭代处理。

超时的话，先检查是不是枚举上限没取 min。我有一次没有写limu = min(sz[u], k)，结果在小数据上一切都对，一到大数据就 TLE，查了好久才发现是 O(n k^2) 退化导致的。

5.4 对拍验证的正确姿势

做这类树上计数题，强烈建议写一个暴力程序对拍。暴力做法就是枚举所有 2^n 种放置方案，筛选正好放 k 个且所有点都被覆盖的方案数，n 取 6 到 10 的小数据生成随机树，把 DP 结果和暴力结果对比。

下面是一段很简单的暴力参考思路：

// 暴力枚举所有方案，用于对拍 int brute(int mask) { int cnt = __builtin_popcount(mask); if (cnt != k) return 0; for (int u = 1; u <= n; u++) { bool ok = false; if (mask & (1 << (u - 1))) ok = true; for (int v : g[u]) { if (mask & (1 << (v - 1))) ok = true; } if (!ok) return 0; } return 1; }

生成随机树时，注意要让每个节点的度数自然分布，别总生成一条链，否则对拍只能覆盖一种退化情况，意义有限。

6. 这道题做完之后的一点体会

P4516 最大的价值不只是让你会做一道树形 DP，而是让你真正理解“状态维度”该怎么设计。很多树形 DP 题，转移写不出来不是因为代码能力差，而是因为状态定义本身就有漏洞。做题时我一直在问自己：合并孩子之后，哪些信息会变化，哪些信息保持不变？u 的放置状态不会变，但覆盖状态可能因为孩子而变；父亲放置设备会影响孩子的覆盖条件。把这几个问题想清楚，状态设计自然就水到渠成了。

如果你做完这题还想继续练，可以找几道类似的树上背包题做对比，比如树形依赖背包、树的覆盖计数等，核心思路都是“枚举父节点与子树之间互相影响的条件，再做背包合并”。以后遇到“树上选若干点，要求某些点之间满足某种覆盖或限制关系”的题，就可以直接套用这套方法论。