1. 树形DP实战：谷仓涂色问题解析与C++实现
今天要分享的是一道经典的树形动态规划问题——USACO竞赛中的谷仓涂色（Barn Painting）。这个问题不仅考察了对树结构的理解，还需要灵活运用动态规划技巧来处理颜色约束条件。作为刷题路上的必经关卡，这类题目在各类编程竞赛中频繁出现，掌握其解法对提升算法能力很有帮助。
1.1 问题重述与核心难点
我们有一组N个谷仓，它们通过N-1条路径连接形成一个树结构（无环图）。部分谷仓已经被涂成红、绿、蓝三种颜色之一，现在需要为剩余的谷仓选择颜色，要求相邻谷仓不能同色。我们需要计算所有合法的涂色方案数，结果对1e9+7取模。
这个问题的核心挑战在于：
- 树结构的处理：需要高效遍历并维护节点间的关系
- 颜色约束的传递：父节点的选择会影响子节点的可选范围
- 已涂色节点的固定：部分节点的颜色已经确定，不能更改
1.2 解题思路分析
这类计数问题通常考虑动态规划(DP)解法。对于树形结构，我们采用树形DP，其基本模式是后序遍历：先处理所有子节点，再根据子节点的结果计算当前节点的值。
定义状态：
f[x][c] 表示当节点x涂颜色c时，以x为根的子树有多少种合法涂色方案
状态转移：
对于节点x的每种可能颜色c，其方案数等于所有子节点在颜色不为c时的方案数乘积
边界条件：
如果节点x已经预先涂色为c'，则f[x][c] = 0 (c ≠ c')，f[x][c'] = 1
最终答案：
根节点所有可能颜色的方案数之和
2. 代码实现详解
2.1 数据结构准备
首先我们需要表示树结构。对于节点数达到1e5的情况，使用邻接表是最佳选择：
cpp复制#define maxn 200005 // 通常开两倍空间
int lnk[maxn], nxt[maxn], son[maxn], tot;
这里：
- lnk[x] 记录节点x的第一条边在边数组中的位置
- son[t] 表示第t条边的终点
- nxt[t] 表示下一条与当前边同起点的边
- tot 是边的总数
这种链式前向星表示法在树和图的问题中非常常见，能高效处理大规模稀疏图。
2.2 动态规划核心
DP的核心是一个深度优先搜索(DFS)过程：
cpp复制void Dfs(int x, int fa) {
// 初始化：如果节点已涂色，则只保留该颜色选项
for (int c = 0; c < 3; c++) {
if (f[x][c]) { // 已涂色
for (int j = 0; j < c; j++) f[x][j] = 0;
break;
}
f[x][c] = 1; // 未涂色则初始化为1
}
// 遍历所有子节点
for (int i = lnk[x]; i; i = nxt[i]) {
int y = son[i];
if (y != fa) { // 避免回溯到父节点
Dfs(y, x); // 先处理子节点
// 状态转移
f[x][0] = f[x][0] * ((f[y][1] + f[y][2]) % MOD) % MOD;
f[x][1] = f[x][1] * ((f[y][0] + f[y][2]) % MOD) % MOD;
f[x][2] = f[x][2] * ((f[y][1] + f[y][0]) % MOD) % MOD;
}
}
}
2.3 输入处理与主逻辑
主函数负责读取输入并初始化：
cpp复制int main() {
// 读取节点数n和已涂色数m
n = read(), m = read();
// 构建树结构
for (int i = 1; i < n; i++) {
x = read(), y = read();
add(x, y); // 无向边需要添加两次
add(y, x);
}
// 处理已涂色节点
for (int i = 1; i <= m; i++) {
x = read(), y = read() - 1; // 颜色转为0-based
f[x][y] = 1; // 标记已涂色
}
// 从根节点(假设为1)开始DP
Dfs(1, 0);
// 输出总方案数
printf("%lld", (f[1][0] + f[1][1] + f[1][2]) % MOD);
return 0;
}
3. 关键点解析与优化
3.1 时间复杂度分析
- 树的构建：O(N)
- DFS遍历：每个节点访问一次，O(N)
- 每个节点的状态转移：O(1)
- 总时间复杂度：O(N)
对于N=1e5的数据规模完全可接受。
3.2 空间优化技巧
虽然我们使用了O(N*C)的空间（C=3），但实际上可以进一步优化：
- 滚动数组：由于DFS是深度优先，可以复用空间
- 颜色压缩：用位运算表示颜色约束
但在竞赛中，通常优先保证代码清晰可读，除非遇到极端空间限制。
3.3 常见错误与调试
- 忘记处理无向边：需要添加双向边
- 模运算遗漏：所有加法和乘法后都需要取模
- 根节点选择：题目没有指定根，但树是无向的，任选一个即可
- 颜色编号：注意题目中的颜色是1-based还是0-based
4. 扩展与变式
这个问题有几个常见的变体：
- K种颜色：将3种颜色推广到K种
- 带权涂色：每种颜色有不同的权重，求最优解
- 图结构：如果不是树而是普通图，问题变为图着色，是NP难的
5. 竞赛技巧分享
在实际比赛中处理这类题目时：
- 先画小样例：手动计算3-4个节点的简单情况
- 模块化代码：将DFS和状态转移分开便于调试
- 打印中间结果：对于DP问题，打印部分节点的状态值有助于发现错误
- 边界测试：空树、单节点、全涂色等特殊情况
提示：树形DP的套路通常是后序遍历+状态累积。掌握这个模式可以解决大部分树形计数问题。
6. 完整代码实现
以下是整合了所有细节的完整实现，包含快速输入输出：
cpp复制#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
const int MOD = 1e9 + 7;
int n, m, x, y;
int lnk[maxn], nxt[maxn], son[maxn], tot;
long long f[maxn][3];
inline int read() {
int ret = 0, f = 1; char ch = getchar();
while (ch < '0' || ch > '9') { if (ch == '-') f = -f; ch = getchar(); }
while (ch >= '0' && ch <= '9') ret = ret * 10 + ch - '0', ch = getchar();
return ret * f;
}
inline void add(int x, int y) {
nxt[++tot] = lnk[x]; lnk[x] = tot; son[tot] = y;
}
void dfs(int x, int fa) {
// 处理初始状态
for (int c = 0; c < 3; c++) {
if (f[x][c]) { // 已涂色
for (int j = 0; j < 3; j++)
if (j != c) f[x][j] = 0;
break;
}
f[x][c] = 1; // 未涂色
}
// 遍历邻接节点
for (int i = lnk[x]; i; i = nxt[i]) {
int y = son[i];
if (y == fa) continue; // 跳过父节点
dfs(y, x); // 递归处理子节点
// 状态转移
f[x][0] = f[x][0] * (f[y][1] + f[y][2]) % MOD;
f[x][1] = f[x][1] * (f[y][0] + f[y][2]) % MOD;
f[x][2] = f[x][2] * (f[y][0] + f[y][1]) % MOD;
}
}
int main() {
n = read(), m = read();
// 构建树结构
for (int i = 1; i < n; i++) {
x = read(), y = read();
add(x, y); add(y, x); // 无向边
}
// 处理预涂色
for (int i = 1; i <= m; i++) {
x = read(), y = read() - 1; // 颜色转为0-based
f[x][y] = 1;
}
// 执行DP
dfs(1, 0);
// 输出结果
printf("%lld\n", (f[1][0] + f[1][1] + f[1][2]) % MOD);
return 0;
}
7. 实战心得
在解决这类树形DP问题时，我总结了几个关键经验：
- 状态定义要明确：f[x][c]的定义直接影响整个解题思路，开始编码前务必想清楚
- 转移方程要验证：用简单例子手动验证状态转移是否正确
- 模运算要彻底：所有加法和乘法后都要取模，避免中间结果溢出
- 递归深度要注意：对于大型树结构，递归实现可能导致栈溢出，可以改用显式栈或BFS式DP
这道题看似简单，但涵盖了树形DP的典型模式。掌握后可以解决许多变种问题，比如：
- 树上的最大独立集
- 树上的最小顶点覆盖
- 带权树形DP问题
在实际比赛中，建议将这类经典问题的代码模板化，但更重要的是理解其背后的思想，这样才能灵活应对各种变式。