第一次跟“叶子的染色”正面相遇是在一本通题库里后来发现洛谷P3155也在考同一道题。当时看完题面第一反应是这不就是给叶子染个色嘛有什么好DP的真动手之后才发现“路径上第一个有色节点”这半句话才是整道题最大的坑。这道题是一个很经典的树形动态规划适合刚学完DFS、准备啃树形DP的人用来练“状态压缩直觉”。题面不复杂但如果你没理解“祖先染色会覆盖整棵子树”很容易把状态设计成三维甚至四维最后把自己绕晕。我这一篇不打算贴一堆状态转移唬人就围绕一个关键点展开为什么一个f[u]就够了以及在实现里哪些细节最容易翻车。1. 先把题意翻译成人话1.1 题面里最容易读错的一句话原题的约束是每个叶子节点有一个需要的颜色。对于每个叶子从根到它的路径上第一个被染色的节点的颜色必须等于这个叶子需要的颜色。注意几个关键词“第一个被染色”是按从根往叶子走的方向数而不是从叶子往根数。它没有说叶子本身必须被染色只是说路径上第一个有色节点颜色要吻合。我见过很多人读完题第一感觉是“叶子必须染”于是答案至少是叶子数量 m。这样题目就退化成一个没有意义的数字游戏显然不是出题人本意。正确理解是只要某个祖先染成了叶子需要的颜色这个叶子自己是可以不染的。比如一条链 根-x-y-叶子叶子要0你可以只染根也可以只染叶子答案都是1如果你染中间的x一样满足。这跟“叶子必须染”是两码事。至于为什么“第一个”是根方向的第一个其实按日常语言“从根到叶子的路径上第一个有色节点”本来就是从路径起点开始数。如果理解成离叶子最近的那个很多转移方程都会反过来样例都不好过。1.2 染色节点就是一把伞一染遮百叶把每个染色节点想象成一把撑开的伞。这把伞的伞面覆盖以它为根的整棵子树。一旦这把伞撑在某个位置所有在这棵子树里的叶子抬头看见的第一个颜色就是伞的颜色。所以这把伞的颜色必须和伞下每一个叶子的需求色一致只要有一个叶子颜色不同这个染色节点就是非法的。这个比喻能解释很多东西如果一片叶子头顶已经有伞那么它自己不需要再染色。因为路径最前面的有色节点已经出现了。如果u染色那么u的所有后代节点都没有必要染色因为它们的任何染色都发生在“已经看见一把伞”之后对叶子来说完全无效。如果一片叶子在多个染色节点的伞面交叠区域只有最靠近根的那把伞起作用。所以一次染色的实际效果是用1个节点“替换”一整片同色叶子的染色需求。树的层次越高一片单色叶子区域就越大用1个节点覆盖就越划算。这就是这道题优化空间的存在。1.3 为什么最优解里不会出现祖先和后代同时染色根据上面的伞模型如果祖先A已经染色后代B再染色那么B的伞完全被A的伞盖住B的存在不会被任何叶子感知到因为叶子看到的第一个有色节点是A。去掉B之后所有叶子的条件仍然满足但染色数少了一个。因此任何最优方案都可以调整成“染色节点两两之间没有祖先关系”的方案。这个性质非常重要它让问题可以切割成互不干扰的子问题如果当前节点u不染色那么它的每一个儿子子树都必须各自独立解决叶子的需求因为两边叶子看到的第一个有色节点分别出现在各自的子树里。如果u染色那么它直接覆盖整棵子树子问题彻底结束不再向下递归。有了这两个互斥的大方向就可以设计DP了。2. 状态设计一个 f[u] 就够了2.1 给 f[u] 一个严格的定义设f[u]表示在“祖先不帮忙”的假设下以 u 为根的子树独立解决问题所需的最少染色节点数。“祖先不帮忙”指的是从根到u的路径上没有已染色节点因此u子树内的叶子不能指望祖先来覆盖必须由u子树内部的染色节点来满足条件。祖先是否染色会影响子树最终要不要染色这是树形DP里很容易踩的后效性。我们的做法是在转移时把“如果u染色”的收益一次性算清把它覆盖的所有子问题全部吞掉这样每个子树的f值就只代表“自己独立存活”的成本不依赖外部环境。对于整棵树答案就是f[root]因为根没有祖先它只能靠自己。2.2 两个选择三种写法对于非叶子节点u只有两种大方向。方向一u不染色。那么u不会对任何叶子产生覆盖每个儿子子树必须独立解决。代价sumF Σ f[v] (v 是 u 的儿子)方向二u染色。u染成0或1。无论染成哪种颜色都要求u子树中的所有叶子需求颜色一致且就是这个颜色。如果满足代价为1。为什么代价是1而不是1 Σ f[v]因为只要u染色u就是所有后代叶子路径上第一个有色节点所有后代节点再染色都是多余的。前面1.3已经证明最优解不会保留多余的后代染色。所以你只需要花1个节点整棵子树都交差。于是转移式可以写成f[u] min( sumF, 1(当子树全0), 1(当子树全1) )注意“全0”和“全1”不可能同时成立除非子树没有叶子但非叶子节点子树必包含叶子。所以实际最多只有一个1被考虑。拿一个最简单例子验证。根节点是3两个孩子1、2都是叶子1要02要1。此时f[1]1, f[2]1根子树不是单色不能染根答案2。如果1、2都要0则根子树全0可以只染根答案1。这个差异就是“伞”的价值。2.3 叶子节点单独处理的原因叶子节点l没有儿子如果套用方向一“u不染色”sumF0这会得到一个非法答案0树里没有任何染色节点叶子路径上根本没有有色节点。所以叶子只能选择方向二也就是染自己f[l]1。实现上我们可以在进入叶子时直接返回f[u] 1; has0[u] (col[u] 0); has1[u] (col[u] 1);有的写法会先把res设成INF再走统一的单色判断同样能得到1。两种都可以关键是不要让叶子得到0。2.4 和洛谷题解里三状态DP的关系很多题解会写三个状态dp[u][0] 1 Σ min(dp[v][0], dp[v][2]) dp[u][1] 1 Σ min(dp[v][1], dp[v][2]) dp[u][2] Σ min(dp[v][0], dp[v][1], dp[v][2])这个DP本身没问题但初学者很容易把dp[u][2]误解成“u不染色时的答案”然后发现dp[u][0]的转移里儿子不染色为什么只用dp[v][2]而不用dp[v][0]绕来绕去。实际上三状态DP是把“祖先是否已经染色”这一维藏进了不同状态里dp[u][0]和dp[u][1]相当于“u染色假设它是当前子树内第一个挡箭牌”时的代价。dp[u][2]则相当于“u不染并且希望祖先不覆盖它让儿子们各自处理”的代价。把它展开成我们这一维状态最后化简就是上面的min(sumF, 1)形式。所以胡写状态之前先用伞模型把覆盖关系画清楚会省很多力气。竞赛里你写三状态也能AC但如果你能说出每个状态的实际含义调试时会顺手很多。3. C 代码实现与踩坑记录3.1 建树时先搞清楚根和叶子的编号题目习惯把节点1到m作为叶子节点n作为根n一般不是叶子。输入是无向边我们无脑建双向邻接表然后从n开始DFS。注意输入顺序洛谷P3155和一本通P1583都是先给n-1行边再给m个叶子的颜色。代码里不要习惯性地把颜色读在边前面。如果你拿到的题面顺序不同就把输入段对调。叶子颜色的数组只需要开m大小但下标是节点编号所以我习惯直接开成MAXN大小把col[i]存在节点i上给DFS叶子判断时直接用不用再做“第i个叶子对应节点i”的映射因为本题叶子编号就是1..m。3.2 完整代码下面给出我实际提交能过的版本。注释尽量写给新手看。// 洛谷 P3155 / 一本通 P1583 叶子的染色 #include bits/stdc.h using namespace std; const int MAXN 10005; int n, m; int col[MAXN]; // 叶子的需求颜色0 或 1 int f[MAXN]; // 子树独立解决的最小染色数 bool has0[MAXN], has1[MAXN]; // 子树内是否存在需要0/1的叶子 vectorint e[MAXN]; void dfs(int u, int fa) { // 题目保证 1..m 全是叶子 if (u m) { f[u] 1; // 叶子只能靠自己必须染一次 if (col[u] 0) has0[u] true; else has1[u] true; return; } int sumF 0; for (int v : e[u]) { if (v fa) continue; dfs(v, u); has0[u] | has0[v]; has1[u] | has1[v]; sumF f[v]; } // 方向一u 不染色每个儿子自己解决 int res sumF; // 方向二u 染色前提是子树内所有叶子颜色一致 // 子树全为 0 if (has0[u] !has1[u]) res min(res, 1); // 子树全为 1 if (has1[u] !has0[u]) res min(res, 1); f[u] res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; // 先读边再读叶子颜色注意顺序 for (int i 1; i n; i) { int a, b; cin a b; e[a].push_back(b); e[b].push_back(a); } for (int i 1; i m; i) cin col[i]; // 题目指定的根是 n不是 1 dfs(n, 0); cout f[n] \n; return 0; }代码不长但有几个点值得展开u m判断叶子这是由题目保证的不是通过度数判断。如果你写deg[u]1根在只有两个节点的极端情况可能被误判成叶子因为此时根n的度数也是1。has0[u]和has1[u]分别表示子树内是否存在需求为0和需求为1的叶子。如果has0 !has1说明子树全要0如果has1 !has0说明全要1两个都是true说明非单色。sumF是“u不染色”的代价。这里不需要把res初始成INF因为我们已经把叶子特判掉了非叶子节点一定可以有“不染色”方案。但如果你要统一处理叶子就必须把res初始成INF否则会翻车。3.3 复杂度与运行规模DFS每个节点只访问一次每条边被枚举两次邻接表复杂度O(nm)。这类题n一般不超过10^5开int足够如果出题人搞到10^6递归DFS要小心栈溢出可以手写栈后序遍历但思路不变。空间上三个数组col/f/has0/has1都是O(n)邻接表也是O(n)。3.4 最容易出错的三个实现细节第一个是叶子特判的位置必须放在进入DFS后、遍历儿子之前。如果放在后面叶子会被当成内部节点处理sumF0会污染答案。第二个是单色判断用“且有且仅有一种需求”这个条件不是“只要有一个has为true就单色”。如果你写if (has0[u] || has1[u]) res min(res, 1)那非单色的子树也会被错误地允许染u答案会偏小。第三个是根别写错。题目指定根是n不是1。有些同学从上到下读完边后顺手就从1开始DFS样例可能碰巧对但换一组数据就WA。我自己的习惯是在主函数里先写注释“根是n”然后再写DFS调用。4. 常见问题与调试方法4.1 样例输出总比答案小1如果你发现程序输出总是比手算少1十有八九是叶子节点被算成了0。检查代码叶子节点有没有特判如果没有在统一逻辑里res sumF 0然后单色判断min(0,1)0叶子就被免费了。这会导致每条叶子分支少算1个染色节点正好是“少1”。解决方法很简单在DFS开头加叶子特判或者把res初始值设为INF后再统一走一遍单色逻辑。4.2 输入顺序带来的“颜色全乱”常见症状程序跑出来的答案离奇比如根明明能只染1个但输出3。在调试时先用一个循环把col[1..m]输出出来看是不是你输入的颜色。如果发现col[1]变成了某个边的端点说明你把颜色读在边之前了导致边把颜色数组覆盖掉。题目是先边后颜色调整输入段即可。4.3 用度数判断叶子踩坑题目说1..m是叶子节点这是最硬的条件。用deg[u]1判断叶子在一般树上没问题但如果树比较小根也会被误判成叶子。而且原题根是nn通常不靠前你把根当叶子后col下标可能越界。所以我在代码里坚持用u m而不是度数判断。这也提醒我们题面给的“叶子编号1..m”是重要条件不是装饰。4.4 单色信息写错了怎么查单色判断是本代码的另一个命门。可以写一个临时函数在DFS后输出每个节点的has0和has1再手推一下几个子树。比如某个节点有两片叶子分别0和1那么它的has0和has1应该都是true如果只有一个true说明有一个叶子没被统计到很可能是DFS时漏了边或者父节点传参写错导致走了回头路。另外叶子颜色数组如果用错了下标比如把第i个叶子的颜色存到了节点im也会导致has统计错。4.5 根选错会怎样这道题根选错很隐蔽。如果选1为根样例给的数据可能答案不变因为覆盖和最优化可能恰好对称。但只要构造一个根不在叶子中心的树比如让两个不同色的叶子分别位于根的两侧无论根选1还是n答案可能都是2但选的根变成某个叶子时DP中的“子树单色”区域会变得不对称导致答案突然变小或变大。保险起见严格按题面从n开始DFS。如果你不确定题目根是n就把题面多读两遍。信息学奥赛的题目在“根”这个字上经常做文章很多WA都是栽在这里。5. 扩展如果题目改一改状态还成立吗5.1 颜色种类增加如果叶子颜色不只是0和1而是k种我们这套f[u]的定义依然成立但单色判断就得维护整个颜色集合。可以用一个bool数组或者bitset记录子树中出现过哪些颜色染u的合法条件是子树内所有叶子颜色相同也就是颜色集合大小恰好为1。复杂度会多一个k的系数k很大时还可以记录“出现过的前两种不同颜色”因为判断是否单色只需要知道颜色种数是否大于等于2。5.2 染不同颜色有不同代价如果染0的代价是w0染1的代价是w1那么“染u代价为1”这个前提不成立f[u]也无法压缩成不带颜色的单值。这时最好回到三状态DPdp[u][0]表示u染0子树独立的最小代价dp[u][1]表示u染1的最小代价dp[u][2]表示u不染且子树独立的最小代价转移里把w0和w1用上。5.3 覆盖型树形DP的通用思路这道题的核心方法可以推广任何“某个节点染色后会影响整棵子树”的树形DP都先问两个问题——染色节点的影响范围是什么影响范围能不能被整体计算如果影响范围是整棵子树且子树内条件必须一致那么“染这个节点用一个节点替换掉整棵子树的需求”这种思路就会非常高效。做其他覆盖型题目时不妨也先画伞再写方程。我刷这道题的时候第一版写的也是三状态DP样例过了交上去却WA。后来我把每个染色节点画成伞发现我状态里的“不染色”含义没弄清楚把叶子算没了。回到一维状态重写一遍就AC。回头想想所谓“叶子的染色”其实不是叶子染不染的问题而是谁能用最少的伞盖住所有叶子的需求。最后分享一个我的小习惯遇到树形DP先别急着看数据范围先在草稿纸上画一条从根到叶子的链把染色节点放上去逐个验证“路径上第一个有色节点”会怎样变化。这一步看似简单却能过滤掉绝大多数状态设计错误。如果你也在P3155上卡住不妨试试这个办法。