树形动态规划解决染色计数问题详解

1. 题目解析与算法思路

染色计数问题是一个经典的树形动态规划问题，要求计算在相邻节点颜色不同的约束下，整棵树的所有合法染色方案数。我们先从题目本身入手，逐步拆解问题。

1.1 问题重述与理解

题目给定一棵N个节点的树和M种颜色。每个节点有自己可用的颜色集合（颜色子集），要求相邻节点颜色不同。我们需要计算所有满足条件的染色方案数，并对1e9+7取模。

关键约束条件：

• 树结构：无向无环连通图
• 相邻节点：直接通过边连接的节点
• 颜色限制：每个节点只能使用预先给定的颜色子集

1.2 算法选择与思路

这个问题适合使用树形DP（动态规划）来解决，原因如下：

1. 树结构具有天然的递归性质，适合DFS遍历
2. 子问题独立：一个节点的染色方案只影响其子节点
3. 父节点和子节点之间存在明确的约束关系（颜色不同）

核心思路是：

• 自底向上计算每个节点的染色方案数
• 对于每个节点，考虑其所有可能的颜色选择
• 对于每种颜色选择，累加子节点不选该颜色的方案数

2. 数据结构设计与预处理

2.1 输入处理与存储

我们需要高效地存储树结构和每个节点的可用颜色信息：

cpp复制const int N = 5001;
int n, m;
vector<int> tree[N];  // 邻接表存储树结构
bool color[N][N];     // color[i][j]表示节点i是否可用颜色j

输入处理部分：

1. 读取节点数n和颜色数m
2. 读取每个节点的可用颜色，填充color数组
3. 读取n-1条边构建邻接表

2.2 DP状态定义

定义两个关键DP数组：

cpp复制int f[N][N]; // f[u][c]表示以u为根的子树，u染颜色c的方案数
int dp[N];   // dp[u]表示以u为根的子树的总方案数

状态转移关系：

• dp[u] = Σ f[u][c] (对所有可用颜色c求和)
• f[u][c] = Π (dp[v] - f[v][c]) (对所有子节点v，且v≠c)

3. 核心算法实现详解

3.1 DFS遍历与动态规划

算法核心是后序遍历（DFS），先处理子节点再处理父节点：

cpp复制void dfs(int