企业官网建设流程全解析

打卡刷题进入第2783天，恰好撞上编号也是2783的题目，算是刷题生涯里的一点小默契。P3914《染色计数》是一道经典的树形DP入门题，题面很短，一句话就能讲完，但真正动手写的时候，卡住我的不是"不会树形DP"，而是没想清楚一个关键问题：每个节点可用的颜色集合不一样，怎么把"状态"和"可选颜色"干净地对齐。这篇就把我从读题、建模、优化到实现的完整思路整理出来，给一起刷信奥题的朋友做个参考，也适合刚学树形DP、准备从模板题往综合题过渡的读者。

1. 先看懂P3914在问什么：一个节点一个颜色集合的树染色计数

1.1 题面拆成三句话

这道题的核心信息可以浓缩成三个部分。

第一，给了一棵n个节点的树。树的性质很重要：没有环，任意两个点之间只有一条简单路径，这意味着我们可以用递归的方式自底向上处理。

第二，有m种颜色，但每个节点并不是所有颜色都能用。题目会给每个点一个"可选颜色集合"，比如节点1只能用颜色2和3，节点2只能用颜色1，这就让问题比"每个点都能染任意颜色"复杂了一个档次。很多树形DP模板题默认颜色全集对每个点开放，这道题偏偏在每个点上做了限制，处理方式必须跟着变。

第三，相邻两个节点不能染同一种颜色，问整棵树有多少种合法的染色方案，答案对某个大质数取模。

题面看起来人畜无害，但"方案计数"这四个字意味着答案可能非常庞大，不能直接枚举，必须用动态规划把子问题的结果复用到父问题上。

1.2 为什么不能暴力枚举

假设每个节点平均有k种可选颜色，那么暴力枚举所有染色方案的复杂度是k的n次方级别。哪怕k只有2、n只有30，方案数也已经超过10亿，更别说n稍微大一点，或者某些点颜色集合比较大。

所以要换个思路：树上只有相邻关系产生约束，而且树的结构决定了每个子树之间是"隔着当前节点互不干扰"的。把当前节点的颜色固定以后，它的每个孩子子树内部怎么染色，彼此之间完全独立，只需要回避"孩子不能和当前节点同色"这一条规则。这种"固定一点，子树自治"的特征，刚好是树形DP能下手的地方。

1.3 难度定位与前置知识

这道题在网络上的难度标签大约是普及+/提高，但它考的东西比普通模板题要全：状态设计、乘法原理、针对颜色集合的稀疏存储、取模运算，再加上一点用二分查找优化索引的功夫。前置知识需要会建树、会DFS递归、理解树上组合计数里"加法"和"乘法"的区别。如果你已经能独立写出"没有上司的舞会"这类最基础的树形DP，那这道题就是你从入门跨向进阶的一道好关卡。

2. 状态与转移：dp[u][c]是怎么推出来的，为什么要按颜色拆开

2.1 只存dp[u]够不够

第一次做树上染色计数的人，很容易下意识写一个dp[u]表示"以u为根的子树染色方案数"。但这个状态在转移时站不住脚：当我们要合并孩子v的方案时，v能不能选某个颜色，取决于u最后选了哪个颜色。如果dp[u]只是一个汇总后的数字，孩子的方案没法针对"u具体染了什么颜色"做排除。

所以状态必须带上颜色维度。定义dp[u][c]为：以u为根的子树内部，在u被染成颜色c的前提下，子树里所有节点都满足相邻不同色的合法方案数。注意这里有个隐含条件：c必须属于u自己的可选颜色集合，否则这个状态没有意义，直接视为0即可。

每个节点维护一串和可选颜色一一对应的dp值，这就是后面所有优化的基础。理解这一点，再看网上那些"二维数组开到底"的写法，就明白它们其实是在给每个点都开一个长度为m的数组，即使这个点根本不能用某种颜色，数组位置也空着。

2.2 叶子节点和内部节点的差异

处理叶子节点最简单：如果u是叶子，它没有孩子，那么当u染成c时，子树内没有其他节点需要考虑约束，方案数就是1。所以只要c属于u的可选颜色，dp[u][c] = 1。

内部节点就要做乘法了。假设u染成了颜色c，我们来看任意一个孩子v。v不能染c，但可以染它可选颜色集合里的其他任何颜色x。当v染x时，以v为根的子树的合法方案数是dp[v][x]。所以"在u染c的前提下，孩子v这一支能提供的方案数"就是所有x不等于c时的dp[v][x]之和。

不同孩子之间是并列关系，各自独立，所以要把每个孩子的"贡献值"乘起来，得到dp[u][c]。

2.3 "加法"和"乘法"到底怎么区分

学树形DP很容易把加法和乘法搞混，这里我多说几句。

在同一个节点上，选择不同的颜色，是互斥的"或"关系：u要么染红，要么染蓝，不可能同时染两个。所以最后汇总一个节点的答案时，要把该节点所有颜色的dp值加起来。

在不同孩子之间，是"并且"的关系：孩子甲的方案确定后，孩子乙的方案可以独立选择，两者组合起来才是一棵完整子树的一种方案。甲有2种，乙有3种，组合起来就是2乘3等于6种。

把这两条规则写进代码里，就是：计算dp[u][c]时用乘法连接各个孩子，最后计算sum[u]时用加法汇总所有颜色。

2.4 用一条链手推一遍

理论说多了容易飘，拿个具体例子走一遍。考虑一条三个点的链：1-2-3，每个点可选颜色都是{1,2}。

从叶子3开始，dp[3][1]=1，dp[3][2]=1，sum[3]=2。

节点2有两个可选颜色。当2染1时，孩子3不能染1，只能染2，贡献是dp[3][2]=1，所以dp[2][1]=1。同理dp[2][2]=1，sum[2]=2。

节点1接两个孩子？不，这里节点1只有孩子2。当1染1时，2不能染1，贡献是sum[2]-dp[2][1]=2-1=1，所以dp[1][1]=1，dp[1][2]=1，sum[1]=2。

这棵树总共2种染色方案，分别是(1,2,1)和(2,1,2)，和手算结果一致。虽然这个例子太简单，但它把"排除孩子同色"的过程完整展示出来了。

2.5 状态空间怎么存

dp[u][c]里面的c只会在u的可选颜色集合里取。所以完全不需要开一个n乘m的二维数组，只需要让dp[u]是一个和col[u]等长的数组，下标一一对应。这样内存是"每个点实际可用颜色数量之和"，比n乘m小得多。真正写代码时，这种稀疏存储是必须的——因为你不知道出题人会给你多大的m，一旦m到1e5量级，二维数组直接爆内存。

3. 优化点：把"枚举另一方颜色"换成"总和减单色"，一次减法干掉O(m)

3.1 朴素写法的复杂度隐患

如果顺着转移公式直接写，计算dp[u][c]时，对每个孩子v都要枚举v的所有可选颜色x，把它们加起来，再排除x等于c的那一项。伪代码大概是：

for (int c : col[u]) { dp[u][c] = 1; for (int v : children[u]) { int total = 0; for (int x : col[v]) { if (x != c) total += dp[v][x]; } dp[u][c] = dp[u][c] * total % MOD; } }

这个三层循环的复杂度是每个点的颜色数乘孩子数乘孩子颜色数，总计可以到O(n乘以m平方)的级别。当m到几百几千，n再大一点，时间完全撑不住。

我最初写这道题时就是先写了这个朴素版本，结果一提交就发现跑不动。问题不在于DP思路错，而在于"排除一种颜色"这个动作做得太笨了——明明孩子的所有颜色只需要求和一次，我却对每个c都重新扫一遍孩子的颜色。

3.2 核心优化：先求总和，再做减法

换个角度看：孩子v的所有可选颜色的dp值之和，其实是一个固定数字，跟u选什么颜色没关系。所以可以提前算好sum[v] = Σ dp[v][x]。

这样一来，u染c时，孩子v的贡献就是sum[v]减去dp[v][c]（如果c属于v的可选集合），否则就是完整的sum[v]。

注意第二句话：如果c根本不在v的可选颜色集合里，说明v本来就不可能染c，那么u就算染c也不会对v产生任何约束，v这一支的所有方案都可以保留，贡献就是sum[v]。从公式上看，dp[v][c]不存在，视作0，sum[v]-0=sum[v]，完全一致。

这个优化把"遍历孩子所有颜色做排除"降成了"判断一个颜色是否存在于孩子集合里"。外层对col[u]的枚举仍然保留，但内层不再嵌套枚举col[v]。于是总复杂度降到大约O(所有点可选颜色数总和)，每条边对应一次对col[u]的遍历，和m的大小没有直接关系了。

3.3 一段很容易误解的公式

网上很多题解会把转移写成dp[u][c] = Π(sum[v] - dp[v][c])，这个写法省略了一次判断，看起来很简洁，但对新手不太友好：如果c不在v的可选集合里，dp[v][c]是什么？

严谨的做法是：先判断c在不在v的可选集合里。在，就用sum[v]-dp[v][c]；不在，就用sum[v]。代码实现里，我选择用二分查找来判断，虽然多了一个log的常数，但逻辑非常清晰，不容易错。

3.4 取模运算里的负数

sum[v]和dp[v][c]都是取模后的数，sum[v]减去dp[v][c]有可能得到负数。在C++里，负数的取模运算结果仍然是负数，直接乘进答案里就错了。所以减法之后要立刻调整成非负：

ll factor = (sum[v] - dp[v][j] + MOD) % MOD;

这里用long long承接乘法，避免两个int相乘溢出。很多第一次写模运算DP的人会在这两个地方各交一次学费，后面第五章我再集中盘点。

4. 完整C++实现：压缩状态的树形DP代码与注释

4.1 数据结构怎么选

我的做法是三个核心容器：

• col[u]：存节点u的可选颜色，读入后排序、去重；
• dp[u]：和col[u]等长的数组，dp[u][i]对应颜色col[u][i]的方案数；
• sum[u]：dp[u]所有元素求和取模。

为什么排序去重？因为如果有重复的颜色出现在同一行里，它们不会产生新的染色方案，留着只会让dp数组和颜色索引对不上，二分查找也会出问题。排序则让"判断某个颜色是否在某节点的集合里"可以用lower_bound做二分。

为什么不用二维数组dp[n+1][m+1]？当m比较小，比如m小于等于2000，二维数组确实直观，查颜色直接按下标走。但一旦m到1e5，空间就是n乘1e5，根本开不出来。压缩存储以后，内存只和每个点实际可用的颜色总数相关，什么数据范围都扛得住。

4.2 完整代码

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int MOD = 1000000007; int n, m; vector<vector<int>> g; // 邻接表 vector<vector<int>> col; // col[u] 排序去重后的可选颜色 vector<vector<ll>> dp; // dp[u][i] 与 col[u][i] 一一对应 vector<ll> sum; // sum[u] = Σ dp[u][i] % MOD // 二分查找 x 在数组 a 中的下标，不存在返回 -1 int idIn(const vector<int>& a, int x) { auto it = lower_bound(a.begin(), a.end(), x); if (it != a.end() && *it == x) return (int)(it - a.begin()); return -1; } void dfs(int u, int fa) { int k = (int)col[u].size(); dp[u].assign(k, 0); // 当前节点没有任何可选颜色，整棵子树无解 if (k == 0) { sum[u] = 0; return; } // 初值 1，表示每个孩子还没乘进来时的"空乘积" dp[u].assign(k, 1); for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 孩子子树已经无解，当前节点所有颜色方案都为 0 if (sum[v] == 0) { dp[u].assign(k, 0); sum[u] = 0; return; } for (int i = 0; i < k; i++) { int c = col[u][i]; int j = idIn(col[v], c); ll factor; if (j == -1) { // 孩子根本不能用颜色 c，不受约束 factor = sum[v]; } else { // 孩子不能用 c，所以从总和中减去孩子染 c 的方案数 factor = (sum[v] - dp[v][j] + MOD) % MOD; } dp[u][i] = dp[u][i] * factor % MOD; } } sum[u] = 0; for (int i = 0; i < k; i++) { sum[u] = (sum[u] + dp[u][i]) % MOD; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; g.assign(n + 1, {}); col.assign(n + 1, {}); for (int i = 1; i <= n; i++) { int cnt; cin >> cnt; col[i].resize(cnt); for (int j = 0; j < cnt; j++) { cin >> col[i][j]; } sort(col[i].begin(), col[i].end()); col[i].erase(unique(col[i].begin(), col[i].end()), col[i].end()); } // 读入 n-1 条边，建无向图 for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dp.assign(n + 1, {}); sum.assign(n + 1, 0); // 树是无根树，选任意节点当根都可以，这里选 1 dfs(1, 0); cout << sum[1] % MOD << '\n'; return 0; }

4.3 代码里几个容易看漏的细节

第一，读取颜色时，每行第一个数cnt表示这一行后面跟着多少个颜色，不是行号。这个容易和后面的n-1行边搞混，我有一段时间每次读入都把节点编号当成颜色个数读，错了半天才反应过来。

第二，把根固定为1不影响答案。因为染色约束只跟边有关，和哪个点是"根"没有关系。任意指定根以后，父子关系只是决定了DFS的调用顺序，不会改变相邻约束。

第三，孩子sum[v]为0时，当前节点所有dp直接清0并返回。这是剪枝，理论上就算不剪枝，后面所有乘法因子也都会变成0。加上这个判断让代码在无解数据上跑得更快，也让逻辑更清晰。

第四，如果题面给的输入不是无向边，而是每个点的父节点编号，处理方式更简单：把父边当成有向边建图即可，DFS时也就不用判断fa了。核心公式完全不变。

4.4 和二维数组写法对比

有些题解开long long dp[1005][1005]，然后直接dp[u][color]访问，这种写法在m很小时非常痛快。核心转移只有几行：

for (int i = 0; i < k; i++) { int c = col[u][i]; dp[u][c] = 1; for (int v : child[u]) { long long sum = 0; for (int x : col[v]) if (x != c) sum += dp[v][x]; dp[u][c] = dp[u][c] * sum % MOD; } }

这个版本没有做总和减单色的优化，其实还是朴素写法。要是直接在此基础上加sum数组优化，二维数组版本也可以很快。但它的问题始终是空间：m稍微一大，n乘m的二维long long数组就会击穿内存。我建议平时练题就习惯压缩存储的写法，将来遇到m为1e5甚至更大的题，不会措手不及。

5. 边界用例与实战复盘：样例手算、空集合、模运算和爆栈

5.1 用一个三节点样例完整手算

写代码不能光靠感觉，要对着一组小数据把dp表一步步推出来。下面这个例子是我当时用来验证代码正确性的：

节点数n=3，颜色数m=3。 节点1可选颜色{1,2}，节点2可选颜色{1,3}，节点3可选颜色{2,3}。 边：1-2，1-3。

先算叶子。节点2没有孩子，dp[2][1]=1，dp[2][3]=1，sum[2]=2。节点3同理，dp[3][2]=1，dp[3][3]=1，sum[3]=2。

再看节点1。对颜色1来说，孩子2可选集合里有1，因子是sum[2]-dp[2][1]=2-1=1；孩子3可选集合里没有1，因子是sum[3]=2。所以dp[1][1]=1乘1乘2=2。

对颜色2来说，孩子2集合里没有2，因子sum[2]=2；孩子3集合里有2，因子sum[3]-dp[3][2]=1。所以dp[1][2]=1乘2乘1=2。

最后sum[1]=dp[1][1]+dp[1][2]=4。

手动枚举验证一下：1染1时，2只能染3，3可以染2或3，共2种；1染2时，2可以染1或3，3只能染3，共2种。总数4，完全一致。跑这段代码，输出也是4，说明核心转移没问题。

5.2 空可选集和必然无解

如果某个节点一行输入只有0，也就是它没有任何可选颜色，那么整个树一定无解，最终输出0。

代码里处理这个情况的路径有两条：一是当前节点k=0时直接把sum[u]设成0返回；二是某个孩子无条件后，父节点把所有dp置0。这两条路最终会把0一路传到根。要注意的是，一旦发现孩子sum=0就置当前节点为0并return，这个剪枝不会影响正确性，因为0乘任何数都是0，等于提前结束了无效计算。

5.3 单节点和全同色链

单节点树是最小边界。比如n=1，m=5，节点1可选颜色{2,4}。那么方案数就是2，因为只有一个点，染2或染4都合法。代码里叶子节点的sum就是去重后的颜色个数，输出正确。

另一个我常拿来测的边界是一条链，所有节点只有颜色1可选，m=1。如果链只有一个点，答案是1；只要链长大于1，相邻两个点都会被迫同色，答案直接变成0。代码跑起来的过程很典型：叶子sum=1，父节点算孩子因子时sum[v]-dp[v][1]=1-1=0，于是dp[父][1]=0，sum[父]=0，逐层向上传播，最终根输出0。

5.4 实战中反复踩过的几个坑

模运算负数是最常见的一个。sum[v]-dp[v][j]在数学上可能是负数，C++取模后也还是负数，直接参与乘法会得到一个看似随机的错误答案。我的习惯是凡涉及减法取模，立刻写成(x % MOD + MOD) % MOD，不要等到出错再回头改。

第二个坑是乘法溢出。两个int相乘已经可能超过int范围，取模前先转成long long。我在代码里把dp和sum都声明成了vector<long long>，乘法表达式里的因子自动提升为long long，这样就安全了。

第三个坑是递归深度。当树的形态是一条长链，n到几万甚至更大时，递归DFS有爆栈风险。如果遇到这种情况，可以把递归改成显式栈做后序遍历，先处理所有孩子再处理当前节点，转移公式完全不变。做OJ题时我会先看一眼题目的n上限，再决定要不要用迭代版。

第四个坑是读入问题。题目给的n行颜色集合，每行以颜色个数开头，这个格式和普通"第一行n m，后面n行每行若干个数字"是有区别的。我用cin >> cnt先把个数读掉，再循环cnt次读取具体颜色，顺序上不要颠倒。

5.5 做完这道题的一点体会

对我来说，P3914最大的价值不是"学会了树形DP"，而是把三个通用技巧练扎实了：判断状态需不需要加维度、用整体总和减单项来避免二层枚举、以及用压缩存储应对不确定的数据范围。尤其是第三点，很多树形DP题目在状态设计上都喜欢搞"每个点只有少量可选值"这种设定，压缩存储配合二分查找几乎是标准解法。

如果你正在刷题打卡，建议不要只盯着AC，试着把这份代码的时间复杂度算清楚，再想想如果题目变成"每个点不能和相邻点以及次相邻点同色"，状态要怎么扩展。把一道题吃透，比泛泛刷十道题有用得多。