零几年的一本通和现在的洛谷上都能看到《叶子的染色》这道题，仔细一读才发现它根本不是“给叶子涂色”那么简单，而是一道非常典型的树形DP：一棵无根树上，所有叶子的目标颜色已经给定，你可以给任意节点染黑或白，一个节点一旦被染色，从它往下到各个叶子的“最终颜色”就会被它接管，只有更深处的染色节点才能覆盖它。题目就在一本通P1583，洛谷对应编号P3155，我当年第一次做的时候状态设计绕了不少弯路，这篇把完整推导、代码和踩坑点都掰开讲清楚。适合刚学完DFS和线性DP、准备啃树形DP的同学。
1. 题目到底在问什么：先读懂“染色覆盖”的规则
1.1 从路径视角看染色规则
题目给的是一个无根树，节点数为 m，每个叶子节点有一个颜色需求，0 代表白，1 代表黑。注意这里只有叶子有“真实需求”，内部节点读入的颜色值没有意义，这是第一个容易踩的坑。
染色规则要说清楚：你可以选择若干节点，给它们染成黑色或白色。对每个叶子来说，从根走到这个叶子的路径上，距离它最近的那个被染色节点，它的颜色就是这个叶子最终显示出来的颜色。换句话说，一个上层节点染色后，它的整棵子树都会“默认继承”这个颜色，但如果某个后代节点又染了色，那这个后代节点管住的叶子就以新颜色为准。
举个小例子：根染成黑色，然后某条分支上的一个叶子自己染成白色，那么这个叶子最终是白色，因为路径上离它更近的是它自己；而其他没有在下方染色的分支叶子，看到的都是根部的黑色。
所以这不是一个“给叶子直接涂色”的问题，而是一个“选尽量少的点，使每个叶子路径上的最近染色点颜色匹配需求”的问题。
1.2 为什么要选一个度数大于 1 的节点当根
题目说“你可以选择一个度数大于 1 的节点作为根”，这句话看起来多余，其实很有讲究。如果选一个叶子当根，那么根到其他叶子的路径定义会变得别扭，而且根自己既是根又是叶子，DP 边界很难处理。要求选内部节点当根，是为了保证根从定义上就有孩子，不是一个末端叶子。
代码实现的时候怎么处理？在建图时统计每个节点的度，找到第一个deg[i] > 1的节点作为根。如果数据里真的出现了所有节点度都不超过 1 的情况，那说明整棵树只有两个节点，这种情况题目基本不会给，但代码里可以随便选 1 号节点兜底。
选根还有一个性质：不管选哪个内部节点当根，最终答案都一样。原因在于这个问题的本质是沿着路径判断“最近染色节点颜色”，它不依赖全局根的具体位置，只要能算清每棵子树的相对关系就行。这个性质不要求读者严格证明，只要记住，写代码时随便找一个度大于 1 的节点就好。
2. 树形DP状态设计：从两个直觉误区到正确答案
2.1 先说说两个常见的错误想法
很多人第一反应是贪心：从叶子往上走，遇到叶子需求颜色和当前“默认颜色”不一致，就给最近能覆盖它的祖先染一下。这种贪心很容易在树形分支多的时候重复计数，而且你很难说清到底在哪个节点染最划算。
还有一种想法是每个叶子都单独染色，需求是 0 的染 0，需求是 1 的染 1，这样一定满足条件，但显然不是最优。比如一整片叶子需求全为 0，只需要在最顶部公共祖先染一次 0 就全解决了。
这两种思路的共同问题是没有把“继承父节点颜色”和“自己染色覆盖父节点颜色”这两个动作建模清楚。树形DP恰好能把这种决策形式化。
2.2 状态定义：附加代价模型
我采用的状态定义是：
dp[u][c]：当“外部最近的有色节点”颜色为 c 时，为了让 u 的子树内所有叶子颜色符合要求，u 自己不染色的情况下，子树内最少还需要新增多少次染色。
这里“外部最近的有色节点”指的是从根到 u 的路径上，离 u 最近的那个真实被染色节点。注意这个节点在 u 上面，可能很遥远，不用管它是谁，只需要知道它的颜色是 c。
这个状态有几个关键点：
- 它不包含外部那个节点的染色次数，那个节点在更高层的决策里已经算过了。
- 它也不包含 u 自己染色的次数，因为状态假设 u 不染色。如果 u 想染色，那就在父节点的转移里作为“覆盖分支”处理。
- 所有状态都是有限且有意义的，不会出现不可行还要用 INF 的情况。因为即使外部颜色和需求完全相反，最差也就是子树里每个叶子都自己染一下，代价不超过叶子数。
2.3 转移：每个孩子只有两条路
考虑 u 的一个孩子 v。现在外部颜色是 c，u 不动，那么 v 子树的叶子最终能不能满足需求，取决于 v 怎么做。
第一条路，v 不染色。那 v 子树继续接受外部颜色 c，所以 v 子树内部需要的新增染色数就是dp[v][c]。这是“继承”分支。
第二条路，v 自己染色。v 可以染成 0，也可以染成 1，染色这个动作本身要付出 1 次代价。v 一旦染色，它就成为 v 子树内新的“外部最近有色节点”，不管原来祖先颜色是什么都被覆盖了。此时 v 子树内部还需要dp[v][0]或dp[v][1]的附加代价，最终是1 + min(dp[v][0], dp[v][1])。这是“覆盖”分支。
每个孩子独立决策，所以 u 的两个状态可以写成：
dp[u][0] = sum( min( dp[v][0], 1 + min(dp[v][0], dp[v][1]) ) ) dp[u][1] = sum( min( dp[v][1], 1 + min(dp[v][0], dp[v][1]) ) )很多初学者会把第二个式子写成sum( min(dp[v][0], dp[v][1]) )，那就少了每次覆盖时孩子自己染色的那 1 次，答案会偏小。
2.4 叶子边界为什么不是 INF
叶子没有孩子，所以叶子只有一条路：要么接受外部颜色，要么自己染色。
设叶子需求颜色为 need，那么：
dp[leaf][need] = 0 // 外部颜色刚好对，什么都不用新增 dp[leaf][1-need] = 1 // 外部颜色不对，叶子自己染一次这个边界和很多题解里的dp[leaf][need]=1, dp[leaf][1-need]=INF不一样，是因为状态定义不同。我的状态是“u 自己不染色时的附加代价”，所以叶子在外部颜色正确时附加代价是 0；如果外部颜色不对，它自己染一次，代价是 1。这个边界写起来更自然，还不需要 INF 的溢出问题。
2.5 根节点为什么一定要强制染色一次
根没有祖先，它没有“外部最近有色节点”可用，所以根自身必须成为提供颜色的真实节点。答案就是：
ans = 1 + min(dp[root][0], dp[root][1])这个 1 是根染色的代价。可能有人会问，如果最优方案里根恰好没染色怎么办？答案是根不染色的方案不会优于根染色的方案：根不染色时，每条孩子子树里都必须自己产生染色节点，等价于每个孩子都走“覆盖分支”；而根染色后，孩子可以选择继承根的颜色，这样可以省下大量重复染色。实际手算几个例子也会发现，根染色要么更优，要么至少不差。
3. 手算实例：每一步转移都能对上答案
3.1 构造一棵七节点树
为了把转移过程看清楚，我构造下面这棵树：
1(根) / \ 2 3 / \ | 4 5 6节点 4、5、6 是叶子，颜色需求分别为：
- 4 需要 0
- 5 需要 1
- 6 需要 1
节点 2 是内部节点，有两个叶子孩子。节点 3 也是内部节点，只有一个叶子孩子 6。根是 1。
下面从叶子开始自底向上算。
3.2 叶子边界直接算
叶子 4 需求是 0：
dp[4][0] = 0 dp[4][1] = 1叶子 5 需求是 1：
dp[5][0] = 1 dp[5][1] = 0叶子 6 需求是 1：
dp[6][0] = 1 dp[6][1] = 03.3 计算内部节点 2
节点 2 的孩子是 4 和 5。先算覆盖分支的公共量：
k4 = 1 + min(dp[4][0], dp[4][1]) = 1 + 0 = 1 k5 = 1 + min(dp[5][0], dp[5][1]) = 1 + 0 = 1然后分别算 dp[2][0] 和 dp[2][1]：
dp[2][0] = min(dp[4][0], k4) + min(dp[5][0], k5) = min(0, 1) + min(1, 1) = 0 + 1 = 1 dp[2][1] = min(dp[4][1], k4) + min(dp[5][1], k5) = min(1, 1) + min(0, 1) = 1 + 0 = 1这个结果说明：无论外部颜色是 0 还是 1，节点 2 的子树都只需要额外染 1 个节点。外部为 0 时叶子 5 得自己染成 1；外部为 1 时叶子 4 得自己染成 0，非常对称。
3.4 计算内部节点 3
节点 3 只有一个叶子孩子 6：
k6 = 1 + min(dp[6][0], dp[6][1]) = 1 + 0 = 1 dp[3][0] = min(dp[6][0], k6) = min(1, 1) = 1 dp[3][1] = min(dp[6][1], k6) = min(0, 1) = 0外部颜色是 1 时节点 3 的子树什么都不用加，叶子 6 直接继承；外部颜色是 0 时叶子 6 自己染一次，代价 1。
3.5 根节点汇总
节点 1 的孩子是 2 和 3。先算：
k2 = 1 + min(dp[2][0], dp[2][1]) = 1 + 1 = 2 k3 = 1 + min(dp[3][0], dp[3][1]) = 1 + 0 = 1然后：
dp[1][0] = min(dp[2][0], k2) + min(dp[3][0], k3) = min(1, 2) + min(1, 1) = 1 + 1 = 2 dp[1][1] = min(dp[2][1], k2) + min(dp[3][1], k3) = min(1, 2) + min(0, 1) = 1 + 0 = 1最终：
ans = 1 + min(dp[1][0], dp[1][1]) = 1 + min(2, 1) = 2对应的最优方案是：根染成 1，叶子 4 染成 0。检查一下：叶子 4 的最近染色节点是自己，颜色 0，满足；叶子 5 的路径上只有根染的 1，满足；叶子 6 的路径上也只有根的 1，满足。一共染 2 个节点，答案正确。
3.6 如果根染成 0 呢
再看另一个选择：根染成 0。那叶子 5 必须自己染成 1，叶子 6 也必须自己染成 1，总代价是根 1 次加两次叶子染色，一共 3。所以根染 1 才是正解。这个例子清楚展示了为什么需要在两个状态里取 min。
4. 完整C++实现：从建树到输出答案
4.1 代码
我给出完整可提交的 C++ 代码，注释尽量详细。
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; int n, root; vector<int> g[MAXN]; int col[MAXN], deg[MAXN]; // col 存的是叶子需求颜色 int dp[MAXN][2]; void dfs(int u, int fa) { // 无根树里，叶子就是度数为 1 的节点 // 根保证度数大于 1，所以根不会被当作叶子 if (u != root && deg[u] == 1) { dp[u][0] = (col[u] == 0 ? 0 : 1); dp[u][1] = (col[u] == 1 ? 0 : 1); return; } dp[u][0] = dp[u][1] = 0; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // v 自己染色接管子树，代价是 1 次染色 + 子树内部附加代价 int cover = 1 + min(dp[v][0], dp[v][1]); // 外部颜色是 0 时，v 可以选择继承或覆盖 dp[u][0] += min(dp[v][0], cover); // 外部颜色是 1 时，v 同样可以选择继承或覆盖 dp[u][1] += min(dp[v][1], cover); } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 1; i <= n; i++) cin >> col[i]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); deg[u]++; deg[v]++; } // 找一个度数大于 1 的节点当根，题目保证存在 root = 1; for (int i = 1; i <= n; i++) { if (deg[i] > 1) { root = i; break; } } dfs(root, 0); // 根没有外部祖先，必须自己染一次色 int ans = 1 + min(dp[root][0], dp[root][1]); cout << ans << '\n'; return 0; }4.2 代码逻辑和细节
deg[u] == 1判断叶子是最稳的，因为无根树的叶子本身就是度数 1 的节点。题目保证根度数大于 1，所以不用担心把根误判成叶子。如果你不放心，可以在 DFS 参数里多传一个根标记，或者把根特判处理。
cover这个变量建议大家先算出来，避免写两遍很长的表达式。它表示“孩子 v 自己染色”的总代价，与外部颜色 c 无关，因为 v 染色后外部颜色没有任何影响。
dp[u][0]和dp[u][1]都要初始化为 0，因为 u 自己不染色，所以当前节点没有新增计数，只是累加孩子的结果。
4.3 复杂度
每个点只会被访问一次，转移是 O( deg[u] ) 的常数操作，总复杂度 O(n)。空间上邻接表加 dp 数组也是 O(n)。n 到 10 万级别的数据，跑起来非常轻松。
5. 踩坑记录与调试思路：为什么你的答案总差一个 1
5.1 把读入的颜色当成所有节点的真实颜色
这是最开始最容易犯的错。题目只保证叶子节点的颜色是真实需求，内部节点的输入颜色是无效的。所以建树之后必须先判叶子，只对叶子取颜色。如果你在内部节点上也用读入的颜色做边界，答案会完全错乱。
调试技巧：在小样例里打印每个节点的deg[u]和是否被当成叶子处理，立刻能看出来问题。
5.2 状态混乱导致答案多算或少算
网上题解里有的状态是“u 强制染色，计入自身代价”，有的状态是“u 不染色，只算附加代价”。两种状态写出来长得有点像，但转移和答案差不少。如果抄错定义，最常见的就是答案整体差 1，或者每个内部节点都额外算了一次自己的染色。
我的建议是：写代码之前先在纸上把状态定义原样写出来，然后对着定义检查三个东西：
- 叶子边界有没有包含自身染色的代价；
- 覆盖分支那个 1 有没有加；
- 最终答案是否需要额外加根染色的 1。
如果三个都对不上，别急着调代码，先回去看状态定义。
5.3 根的选择影响判断
有人会把根选成 1 号节点，但 1 号节点可能是叶子。这个题虽然说了可以选择度大于 1 的节点当根，但你没有必要死磕 1 号节点。代码里遍历一遍找第一个度大于 1 的节点就好。
如果根是叶子，DFS 里它会被误判成叶子边界，然后 dp 值全是 0，答案变成 1，完全错误。
5.4 递归深度可能爆栈
当树退化成一条长链时，递归 DFS 深度会达到 n，很多评测环境默认栈空间不够，会出现莫名奇妙的“段错误”。两个解决办法：
方法一：在本地运行或评测环境允许的前提下，把栈空间加大，比如 Linux 下执行ulimit -s unlimited，但这在 OJ 上不可控。
方法二：改成手写栈做后序遍历。先跑一次 DFS 得到每个节点的父节点和遍历顺序，再逆序处理每个节点。核心思路是：先通过一次迭代 DFS 把节点访问顺序存进数组，然后倒着做 DP，因为 DP 依赖的是孩子先算完。这个方案在任何环境下都稳定。
下面是迭代版的关键片段思路：
vector<int> order; vector<int> parent(n + 1, 0); // 用栈模拟 DFS，得到父节点关系和遍历顺序 stack<int> st; st.push(root); parent[root] = -1; while (!st.empty()) { int u = st.top(); st.pop(); order.push_back(u); for (int v : g[u]) { if (v == parent[u]) continue; parent[v] = u; st.push(v); } } // 逆序做 DP for (int i = n - 1; i >= 0; i--) { int u = order[i]; if (u != root && deg[u] == 1) { dp[u][0] = (col[u] == 0 ? 0 : 1); dp[u][1] = (col[u] == 1 ? 0 : 1); continue; } dp[u][0] = dp[u][1] = 0; for (int v : g[u]) { if (parent[v] != u) continue; int cover = 1 + min(dp[v][0], dp[v][1]); dp[u][0] += min(dp[v][0], cover); dp[u][1] += min(dp[v][1], cover); } }注意遍历顺序是栈式 DFS，所以order不一定是严格的先序遍历，但父节点一定先于子节点进入数组，所以倒序遍历时孩子一定先于父节点被处理。
5.5 对拍检验
这道题很适合写一个暴力程序对拍：直接枚举树上的染色集合，验证每个叶子路径上的最近染色节点颜色，然后取最小染色数。数据规模小的时候暴力完全可行。把暴力答案和 DP 答案对比，能快速暴露状态转移的错误。我第一次写转移时忽略了覆盖分支的 1，就是靠三个节点的随机小树对拍抓出来的。
6. 从这道题带走的通用套路：继承与覆盖模型
6.1 识别树上的路径约束问题
《叶子的染色》看起来是一个“给节点染色”的问题，本质上是一个“路径终点颜色约束”的问题：对每个叶子，从根到它的路径上最后一个染色节点的颜色必须匹配需求。
这类问题有个很通用的解题框架：把每个子树看作一个独立模块，子树唯一需要对外表达的信息，就是“外部提供一个颜色 c 时，子树还需要多少额外操作”。然后当前节点只需要决策两件事：继承外部状态，还是覆盖外部状态。
这个“继承或覆盖”的二分决策，比具体是染色还是放守卫还是选起点更本质。很多树上 DP 的困难都只在状态定义的一念之差。
6.2 换到其他题目怎么迁移
如果题目变成每个节点可以染 k 种颜色，转移就会从 min(dp[v][0], dp[v][1]) 变成对 k 种覆盖状态取 min，复杂度从 O(n) 变成 O(n * k^2)。如果题目要求的是最大收益而不是最少次数，把一个“1 + min(...)”改成“w(u) + max(...)”就行。核心结构没有变。
如果题目不给“选根自由”，而是规定了某个根，也完全不影响这个 DP，因为根只是提供顶层颜色的入口而已。
6.3 我自己做题的一点体会
树形DP最怕在状态定义上摇摆不定。我后来养成了个习惯：无论多小的树，先手算一个三四个节点的样例，把所有 dp 值在纸上列出来，和暴力结果对照一次。确认定义没问题再写代码。这个过程看着慢，实际是省时间的，因为树形DP的 bug 往往不在语法，而在逻辑。
如果你现在卡在《叶子的染色》这道题上，建议先别急着抄代码，拿一张纸画一棵六七节点的树，把第一节里的例子自己推一遍。推完之后再回来写代码，你会发现状态转移突然就顺了。
