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(
