树形DP精讲：从连通子图计数到蓝桥杯国赛真题解析

1. 项目概述：从一道国赛真题说起

最近在复盘历年蓝桥杯国赛的真题，尤其是数据结构与算法相关的题目，发现“Who killed Cock Robin”这道题出现的频率相当高，讨论热度也一直不减。这不仅仅是因为它有一个引人遐想的名字，更因为它精准地考察了选手对树形结构和动态规划（DP）的深刻理解与灵活应用能力。简单来说，这道题的核心是：给定一棵树，我们需要计算这棵树中所有连通子图的数量。听起来似乎不难？但当你真正动手去实现，尤其是追求高效解法（通常要求时间复杂度在O(n)或O(n log n)）时，就会发现里面门道很深，涉及到对树形DP状态定义的精准把握、转移方程的巧妙设计以及对组合数学的基本运用。

这道题非常适合作为备战高阶算法竞赛的经典例题。它不像一些偏门的“脑筋急转弯”式题目，其考察的知识点——树、DP、连通性——是算法领域的基石，理解它能极大地提升你解决复杂树形问题的能力。无论你是正在备赛蓝桥杯国赛、ICPC区域赛，还是单纯想深化对树形DP的理解，吃透这道题都会让你受益匪浅。接下来，我将结合自己的解题和教学经验，为你彻底拆解“Who killed Cock Robin”，从问题本质分析到多种解法的实现细节，再到常见的“坑点”和优化技巧，希望能帮你把这十分稳稳拿到手。

2. 核心问题解析：什么是树的连通子图？

在深入代码之前，我们必须把问题本身掰开揉碎，理解每一个约束条件和最终目标。

2.1 问题重述与定义

题目“Who killed Cock Robin”通常以如下形式描述：给定一棵包含n个节点的树（树是一种无环连通图），我们需要计算这棵树中所有可能的连通顶点子集的数量。注意，这里的关键词是“连通”和“子集”。

1. 子集：从n个节点中，任意选择0个到n个节点组成一个集合。空集通常也被认为是一个有效的子集（但有时题目会特别说明是否包含空集，经典解法通常包含，最后减去即可）。
2. 连通：被选中的节点集合，在原树结构下，其诱导子图是连通的。也就是说，仅由选中节点以及连接这些节点的原树边构成的图，其中任意两个节点都是可达的。

举个例子：假设有一棵简单的3个节点的链状树：1-2-3。

• 有效的连通子图包括：{}(空集),{1},{2},{3},{1,2},{2,3},{1,2,3}。
• 无效的连通子图：{1,3}。因为节点1和3在原树中不直接相连，需要通过节点2，但节点2未被选中，所以{1,3}这个集合的诱导子图是不连通的。

我们的任务就是计算这个数量，并对一个通常给定的模数（如1e9+7）取模。

2.2 为什么不能暴力枚举？

最直接的想法是暴力枚举所有可能的子集，然后检查每个子集的连通性。一棵树有n个节点，子集总数是2^n个。对于每个子集，检查连通性至少需要O(n)的时间（例如使用BFS/DFS）。总时间复杂度是O(2^n * n)，当n超过20就完全不可行了。蓝桥杯国赛的数据规模，n通常在10^5这个量级，因此我们必须寻找O(n)或O(n log n)的解法。

2.3 树形DP的直觉引入

既然问题是关于树的，而所求的连通子图又与树的局部结构紧密相关，那么树形动态规划（Tree DP）几乎是必然的选择。树形DP的核心思想是“分治”：在树上进行DFS，对于每个节点，我们先解决其所有子树的问题，然后根据子树的结果来组合出当前节点为根的子树的问题的解。

对于本题，一个关键的突破口是：任何一个连通子图，都唯一对应着树上的一个“根”节点（该连通子图中深度最小的节点）。这样，我们可以避免重复计数。我们的DP计划可以定义为：以节点u为根的子树中，选择若干个连通节点，并且强制要求节点u必须被选中，同时整个被选中的部分必须是连通的，这样的方案数是多少？

但这样定义还不够，因为我们需要知道当前连通块是否与上方的父节点相连，这会影响父节点进行状态合并时的决策。因此，经典的树形DP会定义两个状态。

3. 核心算法：树形DP状态设计与转移

这是整个解题过程最精妙的部分。定义的好坏直接决定了转移方程是否简洁、是否容易理解。

3.1 状态定义

我们定义两个DP数组，均定义在以节点u为根的子树范围内：

• dp[u][0]: 在u的子树中，选择若干个节点形成若干棵互不相连的连通子树的方案数。注意，这些连通子树彼此之间没有边连接，并且节点u本身不被选中。你可以把它想象成在u的子树里打了一些“孤立”的连通块。
• dp[u][1]: 在u的子树中，选择若干个节点形成一个连通块，并且这个连通块必须包含节点u的方案数。也就是说，以u为这个连通块的“根”。

为什么定义dp[u][0]？因为它代表了当u不被选中时，其子树可能的所有状态，这是后续进行乘法原理组合的基础。

3.2 状态转移方程

我们采用后序遍历（DFS）的方式计算。假设当前处理节点u，它有几个子节点v1, v2, ..., vk。我们已经计算好了所有dp[v][0]和dp[v][1]。

1. 初始化：

   • dp[u][0] = 1。当u不被选中时，其子树为空（一个节点都不选）是一种方案。
   • dp[u][1] = 1。当u被选中时，仅包含u自己这一个节点的连通块是一种方案。

2. 合并子节点v： 当我们考虑把子节点v的子树状态合并到u时，需要分情况讨论：

   • 对于dp[u][0]（u不被选）： 子节点v的子树可以独立决策，互不影响。因此，对于每个子节点v，它对dp[u][0]的贡献是：(dp[v][0] + dp[v][1])。 解释：在v的子树中，无论v是被选中（dp[v][1]）还是不被选中（dp[v][0]），由于u不被选，v的连通块与u无关，所以v的子树的任何合法选择都可以独立存在。 所以合并过程是乘法原理：dp[u][0] *= (dp[v][0] + dp[v][1])。

   • 对于dp[u][1]（u被选）： 因为u必须被选，并且最终要形成一个包含u的大连通块，那么对于每个子节点v，有两种选择： a.不连接：不将v所在的任何连通块与u连接。那么v的子树的方案数就是dp[v][0]（因为如果v被选了dp[v][1]，那么v所在的连通块就与u的连通块分离了，这违反了“整个是一个连通块”的定义，所以不能是dp[v][1]）。 b.连接：将v所在的某个包含v的连通块与u连接起来。那么v必须被选，且方案数就是dp[v][1]。 因此，对于子节点v，它对dp[u][1]的贡献是：(dp[v][0] + dp[v][1])。 等等，这和dp[u][0]的贡献一样？注意理解，这里的dp[v][1]意味着“选择包含v的连通块并将其连接到u”。因为u已经被选中，连接操作是“允许”的，并且连接后，u和v就在同一个连通块里了，依然满足dp[u][1]“形成一个包含u的连通块”的定义。 所以合并过程同样是：dp[u][1] *= (dp[v][0] + dp[v][1])。

   重要提示：这里是最容易混淆的点。dp[u][1]的转移中，dp[v][1]之所以能被乘进来，是因为它隐含了“v的连通块通过边(u, v)与u连通”这个操作。在树形DP的视角里，当我们处理节点u时，我们只关心子树内部的连通性，以及子树与u的连通关系。dp[v][1]已经保证了v子树内选中的部分是一个包含v的连通块，那么只要u被选中，边(u,v)的存在自然就将这两个连通块合并了。

3. 最终答案： 根据我们之前的分析，每个连通子图都唯一对应一个深度最小的“根”节点。那么，整个树的所有连通子图数量，就等于所有节点的dp[i][1]之和（因为每个连通子图都以其中某个节点为根）。 即：ans = sum(dp[i][1] for i in 1..n)。 通常题目包含空集，如果要求不包含空集，则ans - 1即可。

3.3 一个具体的计算示例

让我们用之前的链状树1-2-3（1-2相连，2-3相连）来手动验证一下。假设以2为根节点（这需要我们先确定一个根进行DFS，通常任意选1即可，但这里为了方便理解，我们假设以2为根，那么1和3都是2的子节点）。

• 叶子节点1和3：dp[1][0] = 1,dp[1][1] = 1dp[3][0] = 1,dp[3][1] = 1

• 节点2： 初始化：dp[2][0] = 1,dp[2][1] = 1处理子节点1：dp[2][0] *= (dp[1][0] + dp[1][1]) = 1 * (1+1) = 2dp[2][1] *= (dp[1][0] + dp[1][1]) = 1 * (1+1) = 2处理子节点3：dp[2][0] *= (dp[3][0] + dp[3][1]) = 2 * (1+1) = 4dp[2][1] *= (dp[3][0] + dp[3][1]) = 2 * (1+1) = 4

• 计算答案：ans = dp[1][1] + dp[2][1] + dp[3][1] = 1 + 4 + 1 = 6。 这对应了：{1},{2},{3},{1,2},{2,3},{1,2,3}。空集{}被包含在dp[2][0]等状态中，但未被计入dp[i][1]，所以如果题目要求包含空集，答案就是6，否则是5。

可以看到，结果与我们之前枚举的完全一致。

4. 代码实现与细节处理

理论清晰后，实现就是水到渠成的事情。但魔鬼总在细节中。

4.1 基础DFS递归实现

#include <iostream> #include <vector> using namespace std; const int MOD = 1e9 + 7; const int MAXN = 100005; vector<int> tree[MAXN]; long long dp[MAXN][2]; // dp[u][0], dp[u][1] void dfs(int u, int parent) { dp[u][0] = dp[u][1] = 1; // 初始化 for (int v : tree[u]) { if (v == parent) continue; // 避免回溯到父节点 dfs(v, u); // 递归处理子树 // 状态转移 dp[u][0] = dp[u][0] * ((dp[v][0] + dp[v][1]) % MOD) % MOD; dp[u][1] = dp[u][1] * ((dp[v][0] + dp[v][1]) % MOD) % MOD; } } int main() { int n; cin >> n; for (int i = 0; i < n - 1; ++i) { int a, b; cin >> a >> b; tree[a].push_back(b); tree[b].push_back(a); } // 任选一个根节点，这里选1 dfs(1, 0); long long ans = 0; for (int i = 1; i <= n; ++i) { ans = (ans + dp[i][1]) % MOD; } cout << ans << endl; // 如果题目明确不包含空集，则输出 (ans - 1 + MOD) % MOD return 0; }

4.2 关键细节与注意事项

1. 取模运算：这是竞赛中最常见的“坑”。必须在每一次加法和乘法操作后立即取模，防止中间结果溢出。特别是(dp[v][0] + dp[v][1])这部分，先加再取模，然后再参与乘法。
2. 树的存储与遍历：使用邻接表（vector<int> tree[MAXN]）存树。DFS时一定要传入parent参数，用于判断回边，避免无限递归。
3. 根节点的选择：对于无根树，任意选择一个节点作为DFS的根即可，结果不变。这是树形DP的一个优美性质。
4. 数据类型：使用long long来存储DP值，因为即使取模，中间乘法计算也可能超出int范围。
5. 初始化：dp[u][0] = dp[u][1] = 1的理解非常关键。它代表了最基础的状态：对于dp[u][1]，就是只选u自己；对于dp[u][0]，就是u不选，其子树全不选（一种方案）。

4.3 复杂度分析

• 时间复杂度：O(n)。每个节点被访问一次，每条边被访问两次（邻接表存无向边），在节点处进行常数时间的转移计算。
• 空间复杂度：O(n)。用于存储树结构的邻接表和DP数组。

这个效率足以应对n高达10^5甚至10^6的数据规模，完全满足蓝桥杯国赛的要求。

5. 思路延伸与变式思考

掌握了基础解法，我们可以看看这个模型能如何变化，这有助于应对可能出现的变种题。

5.1 如果不包含空集怎么办？

正如之前提到的，我们最终求的是sum(dp[i][1])。这个求和包含了所有仅包含一个节点的连通子图（即每个节点自身），但不包含空集。因为dp[i][1]的定义要求必须包含节点i。所以，如果题目要求计算非空连通子图，我们的答案就是sum(dp[i][1])。如果要求包含空集，则需要再加1。务必仔细读题。

5.2 如果树有边权，要求连通子图内边权和满足条件？

这是常见的变式。例如，要求连通子图内所有边的权值和不超过K，或者为某个定值。 此时，我们的DP状态需要增加一维来表示“容量”或“权值和”。 定义dp[u][j][s]：在以u为根的子树中，u是否被选（j=0/1），且已选边权和（或某种度量）为s的方案数。 这变成了一个“树形背包”问题。转移时，需要枚举分配给每个子树的“容量”，时间复杂度会上升到O(n * K^2)（对于每个节点和每个子节点需要枚举容量进行合并）。需要使用上下界优化或卷积优化才能达到O(n * K)或更好。这在国赛难度中属于压轴题范畴。

5.3 如果要求计算所有连通子图的某种属性之和？

比如，求所有连通子图的节点数之和、直径之和等等。 对于这类问题，通常需要改变DP状态的定义，使其不仅能计数，还能维护我们关心的属性信息。例如，求节点数之和： 我们可以定义dp[u][1]为以u为根的连通子图的数量（同原问题），同时定义sz[u][1]为所有以u为根的连通子图的节点总数。 在转移时，当我们将子节点v的连通块（dp[v][1]）连接到u时，它对sz[u][1]的贡献不仅仅是sz[v][1]，还需要考虑dp[v][1]个连通块，每个都因为连接了u而增加了u这个节点（但u只被计算一次，需要仔细处理）。这类问题需要更精细的组合数学推导。

5.4 在DAG（有向无环图）上求连通子图？

树是一种特殊的DAG。在一般的DAG上求连通子图数量是NP-Hard问题，没有多项式时间算法。这反衬了树结构的特殊性使得本题存在优美线性解法的可贵。

6. 常见错误与调试技巧

即便理解了算法，实现时也可能掉进一些陷阱。

6.1 错误类型汇总表

6.2 迭代DFS（栈模拟）实现示例

对于深度可能很大的树，递归DFS是不安全的。以下是使用栈进行后序遍历的迭代方法，它显式地管理调用栈，更稳定。

void dfs_iterative(int root) { vector<int> parent(n+1, 0); vector<int> order; // 存储后序遍历的节点顺序 stack<int> stk; stk.push(root); parent[root] = -1; // 根节点的父节点标记为-1 // 第一步：用栈得到后序遍历序列 while (!stk.empty()) { int u = stk.top(); stk.pop(); order.push_back(u); for (int v : tree[u]) { if (v == parent[u]) continue; parent[v] = u; stk.push(v); } } // 注意：此时order是“伪后序”，是根->子节点的顺序，我们需要逆序处理 reverse(order.begin(), order.end()); // 第二步：按照逆序（即真正的后序）进行DP for (int u : order) { dp[u][0] = dp[u][1] = 1; for (int v : tree[u]) { if (v == parent[u]) continue; dp[u][0] = dp[u][0] * ((dp[v][0] + dp[v][1]) % MOD) % MOD; dp[u][1] = dp[u][1] * ((dp[v][0] + dp[v][1]) % MOD) % MOD; } } }

实操心得：在比赛环境不确定栈空间大小时，尤其是处理链状树（深度=n），使用迭代DFS是更稳妥的选择。虽然代码稍长，但避免了不必要的风险。

6.3 对拍与测试数据生成

要确保代码万无一失，可以写一个暴力程序（用于n<=15的小数据）与你的DP程序对拍。 暴力程序思路：枚举所有2^n个子集，用并查集或DFS检查每个子集的连通性。 生成随机树的方法：可以使用“随机连接”法，对于节点i (i从2到n)，随机选择一个小于i的节点j，连接(i, j)，这样保证生成的是树。

7. 总结与实战建议

“Who killed Cock Robin”这道题是树形DP的经典入门题，但它蕴含的思想却非常深刻。它教会我们如何通过定义“包含根”的状态来唯一标识一个连通块，从而将复杂的全局计数问题分解为可合并的子树问题。

在实战中，遇到这类“树上的计数”问题，可以优先思考：

1. 问题是否具有最优子结构？子树的结果能否用于构建父节点的解？
2. 如何设计状态才能完整描述子树信息，并且便于向上合并？通常状态需要表示“与父节点的关系”（如是否连通）。
3. 转移方程是否考虑了所有情况？务必画出示意图，枚举子节点与父节点连接/不连接的所有可能性。

最后，关于蓝桥杯国赛的备战，这道题给你的启示是：一定要重视基础数据结构的深刻理解和经典模型的内化。树形DP、区间DP、状压DP、最短路、网络流这些经典问题，国赛往往不会直接考裸题，但会进行巧妙的包装或与其他知识点结合。只有把“连通子图计数”这种基础模型吃得透透的，当遇到它的变种时，你才能迅速识别出核心，并灵活调整状态定义。

我个人在训练和教学中发现，很多同学卡在这道题，不是因为DP方程复杂，而是最初对“dp[u][0]”状态存在的必要性理解不到位。记住，dp[u][0]代表了u不被选中时，其子树所能形成的所有独立连通块的方案数，它是保证后续乘法原理正确合并的基石。多找几道类似的树形计数题练习，比如“树上的独立集计数”、“树的连通划分”等，你会对这类问题有更系统的把握。