第一次做“叶子的染色”这题时我把它当成了一道树上的涂色构造题结果想把“叶子染成什么颜色”直接塞进DP越写越晕。后来才反应过来叶子的初始颜色已经给定我们要做的不是自由染色而是“用最小的代价调整叶片颜色让整棵树的根节点变成目标颜色”。叶子只是最底层的可操作对象真正做决策的是那些非叶节点它们的颜色由儿子节点的颜色投票决定。这个模型一清晰DP状态就顺理成章了转移反而变成了一个带贪心的组合问题。这道题在信息学奥赛一本通里是P1583在洛谷对应P3155标签是树形DP但真正拉开差距的地方在第3节那个“先全选0再改1”的贪心证明。适合刚学完树形DP、想找一道综合题练手的同学也适合已经会做、但对“平局任选”和“多数规则”边界理解得不够透彻的选手。1. 先搞清楚题目到底在说什么1.1 核心模型儿子投票父亲继承题目给了一棵无根树其中有若干叶子节点每个叶子有一个初始颜色用0和1表示。我们有一次“调整”的能力把一个叶子的颜色从0改成1或者从1改成0每次代价为1。内部节点自己没有独立颜色。它的最终颜色由它的所有儿子节点的颜色共同决定哪种颜色在儿子里出现得更多这个内部节点就显示成哪种颜色。如果两种颜色数量一样多那么这个节点的颜色可以任意选择既可以算成黑色也可以算成白色。目标很简单通过最少的叶子改动次数让指定的根节点最终显示出目标颜色。有些版本问的是“根为黑色”有些版本问的是“黑或白都行取较小值”本质上是一回事交换0和1后对称所以DP要把两个颜色都算出来最后按题目要求取。这个模型很像一个“投票传导”过程。叶子是投票人内部节点是计票人计票结果向上继续参与父亲的投票。改一片叶子不仅影响自己这个节点还会沿着树上溯影响所有祖先的颜色。这也是为什么不能直接枚举叶子改法必须用树形DP从下往上做。1.2 为什么能自底向上拆成子问题树形DP能成立关键在于“子树的颜色决策可以独立打包”。某个节点u的颜色只取决于它所有儿子的最终颜色。儿子内部怎么改叶子才能变成某个颜色是儿子子树自己的问题一旦儿子子树用最小代价确定了“我这边输出颜色0”和“我这边输出颜色1”各自的花费u就不需要再关心这些叶子具体是哪几片被改了。所以对每个节点我们只需要维护两个数让这个节点的最终颜色是0需要的最小叶子改动数以及让它是1需要的最小改动数。叶子节点的这两个数直接由初始颜色决定内部节点再把儿子的两个数拿过来做组合。这种“每个子树只向外暴露两个状态”的设计是这题作为树形DP入门进阶题的核心价值。如果你感觉这个模型有点抽象可以把它想象成组装电脑每个零件子树告诉你“我要输出黑色需要多少钱输出白色需要多少钱”上一级只负责统计下面那些零件的输出不再关心零件内部的螺丝怎么拧。2. DP状态设计只关心“最终显示成什么颜色”2.1 状态定义与叶子边界设 dp[u][0] 和 dp[u][1] 分别表示在以u为根的子树中通过调整叶子颜色使得节点u最终显示为0或1的最小叶子改动次数。注意这里说的是u的“最终显示颜色”不是u本身被涂成什么。内部节点没有涂色操作颜色完全靠儿子投票产生叶子虽然有初始颜色但可以被改所以叶子节点的dp值本质上是“让这片叶子变成目标颜色需要花多少钱”。如果u是一片叶子初始颜色是 col[u]那么dp[u][col[u]] 0因为叶子现在就是目标颜色不需要改。dp[u][col[u] ^ 1] 1因为要把这片叶子改成相反颜色必须付出1次代价。这个边界很简单但它决定了DP的“代价来源”。所有内部节点的dp值最终都是由这些1和0累加出来的。2.2 为什么状态里不需要记录“节点被染色”很多人一开始会把状态设计成“节点u染成0”或“节点u染成1”这样就错了。叶子染色是唯一的操作内部节点没有“染自己”这个动作只有“儿子颜色多数决定它的颜色”。所以状态里出现的0和1不是“我决定让u显示什么颜色”而是“我希望u最终显示什么颜色”。为了实现这个希望u的儿子们必须适当选择它们自己的最终颜色这个选择又进一步约束更下层的叶子。一层层传下去最后代价体现在叶子的改动次数上。用“希望”而不是“强制”是树形DP里很常见的视角转换。比如有的题目里状态是“u被选中”而这里是“u的结果颜色”。状态定义一旦贴合了题目规则转移推起来就顺畅很多定义反了后面所有推导都会被卡住。3. 转移方程与贪心证明3.1 子问题从每个儿子手里二选一假设节点u有k个儿子分别为 v1, v2, ..., vk。现在我想让u显示成0那么每个儿子 vi 最终显示成0或1都可以但选择0的儿子数量必须不少于选择1的儿子数量。因为平局时u可以任意选择所以只要0的数量不比1的数量少就能让u最终显示成0。每个儿子 vi 如果最终显示0代价是 dp[vi][0]如果最终显示1代价是 dp[vi][1]。于是问题变成了有k个选项每个选项要么选0要么选1选0的个数至少占一半求总代价最小值。这是一个典型的“二选一 数量约束”问题。看起来像背包但因为约束只跟数量有关不跟具体权重有关可以用贪心。3.2 先全选0再考虑把哪些0改成1计算 dp[u][0] 时最朴素的想法是先把所有儿子都按0来选总代价为 sum0 Σ dp[vi][0]。这时0的数量是k肯定满足“0不少于一半”的条件。接下来如果某个儿子从0改成1会带来一个代价增量Δ_i dp[vi][1] - dp[vi][0]总代价 sum0 Σ Δ_i对所有被改的儿子求和每改一个儿子0的数量就减少1。为了最后仍然至少有 ceil(k/2) 个0最多允许改动手中的个数是lim k - ceil(k/2) floor(k/2)所以问题变成了在至多lim个儿子中选出若干个来进行“0改1”使 ΣΔ_i 尽可能小。3.3 为什么只取排序后前lim个负数对于每个儿子Δ_i 可能是正数、负数或0。如果一个 Δ_i 是正数改这个儿子会让总代价变大而且合法的0数量还会减少完全没有好处。所以最优方案一定不会改 Δ_i0 的儿子。如果一个 Δ_i 是负数改它能降低总代价但受限于最多只能改 lim 个。为了在限额内获得最大收益显然应该选负得最多的那些Δ_i。把所有 Δ_i 从小到大排序优先取前面那些负数直到取满lim个或者已经遇到非负数为止。因此dp[u][0] sum0 排序后前lim个负数Δ之和计算 dp[u][1] 完全对称。先全选1代价 sum1 Σ dp[vi][1]从1改成0的增量为 dp[vi][0] - dp[vi][1]同样取前lim个负数加上去。3.4 一个关键的边界平局任选为什么 lim 是 floor(k/2) 而不是别的因为题目中说“平局颜色任选”。以 dp[u][0] 为例如果k2也就是u只有两个儿子那么只要有一个儿子是0另一个是1u的颜色既可以是0也可以是1因为平局。这时候 need ceil(2/2) 1lim 1最多允许改1个0成1。如果题目改成“多数必须严格”那么k2时两个儿子必须都是0u才能显示0lim就变成0需要的代价会完全不同。很多人在这个地方翻过车样例通常也不会把这种偶数节点的平局情况卡出来实际提交时才暴露。所以做题时第一件事就是确认同样多算哪种颜色如果“任选”就用非严格多数如果“取父节点某种固定偏好”或“不能平局”就要用严格多数。洛谷P3155的常见表述里是“可任选”所以上面的 need ceil(k/2) 是对的。4. 完整实现与核心代码4.1 读入数据和根的选择常见题目输入形式是第一行两个整数n和m表示树有n个节点其中编号1到m的节点是叶子。接下来给出n-1条边然后给出m个叶子颜色第i个颜色对应编号为i的叶子。虽然这里用了“叶子编号1..m”的约定但更稳妥的做法还是通过度数判断叶子。不过颜色读取顺序要和题目给出的一致所以代码里先默认第i个颜色给编号i的叶子如果实际题目不是这种格式套的时候把 col[i] 改到对应的节点编号上就行。根的选择可以任意因为题目有一个性质答案与根的选择无关。找一个原树中度数大于1的节点做根就行。如果整棵树全是叶子这种退化情况需要特殊处理一般数据不会给这种形态。4.2 DFS递归实现核心代码如下#include bits/stdc.h using namespace std; const int N 100005; int n, m; vectorint g[N]; int col[N]; bool isLeaf[N]; int dp[N][2]; void dfs(int u, int fa) { if (isLeaf[u]) { dp[u][col[u]] 0; dp[u][col[u] ^ 1] 1; return; } long long sum0 0, sum1 0; vectorint d0, d1; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sum0 dp[v][0]; sum1 dp[v][1]; // 把v从0改成1的代价增量 d0.push_back(dp[v][1] - dp[v][0]); // 把v从1改成0的代价增量 d1.push_back(dp[v][0] - dp[v][1]); } int k d0.size(); if (k 0) { dp[u][0] dp[u][1] 0; return; } sort(d0.begin(), d0.end()); sort(d1.begin(), d1.end()); int lim k - (k 1) / 2; // floor(k/2) long long best0 sum0; for (int i 0; i lim d0[i] 0; i) { best0 d0[i]; } long long best1 sum1; for (int i 0; i lim d1[i] 0; i) { best1 d1[i]; } dp[u][0] best0; dp[u][1] best1; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } for (int i 1; i m; i) { cin col[i]; // 假设叶子编号为1..m按题目顺序读入 } if (n 1) { cout 0 \n; return 0; } for (int i 1; i n; i) { if (g[i].size() 1) isLeaf[i] true; } int root 1; while (root n isLeaf[root]) root; if (root n) { // 整棵树没有非叶节点属于退化情况这里直接结束 cout 0 \n; return 0; } dfs(root, 0); // 若题目固定根为黑色则输出dp[root][0]若任选黑/白则取min cout min(dp[root][0], dp[root][1]) \n; return 0; }代码里有两处容易忽略的细节。第一叶子节点处理完就 return不要继续去循环儿子否则会把叶子当内部节点处理。这里的 isLeaf 判断用的是原树度数和根的选择无关。第二internal节点排序前先判断 k 是否为0。正常非叶节点一定有至少一个儿子但为了代码健壮性加上判断没坏处。如果将来把根固定在某个度数为1的节点上这个判断也能兜住退化情况。4.3 一个小例子验证转移用一个最简单的树验证根节点1有两个儿子2和32和3都是叶子。假设根不是叶子儿子2初始颜色0儿子3初始颜色1目标让根显示0。叶子2dp[2][0]0dp[2][1]1。叶子3dp[3][0]1dp[3][1]0。对于根节点1k2sum0011。要把儿子从0改成1的增量分别是儿子21-01儿子30-1-1lim1三个增量的排序是[-1, 1]只取前1个负数所以 best01(-1)0。这说明两个叶子一个黑一个白时根可以直接利用“平局任选”显示成黑色不需要改任何叶子。这个例子很直观地说明了为什么这里的条件是“0不少于1”而不是“0必须多于1”。5. 复杂度分析与边界情况5.1 复杂度排序看似多其实总规模是O(n log n)每个节点转移时都要对自己儿子列表里的增量排序。把所有节点的儿子数量加起来正好是n-1所以虽然每个节点内部有一个排序但排序总长度是n-1。最坏情况是树的根节点直接连着n-1个儿子一次排序O(n log n)最好情况是二叉树每个节点最多两个孩子很多排序操作对象很小。整体复杂度最坏O(n log n)在n100000的规模下完全够用。空间上只需要存图和dp数组O(n)。如果担心递归栈n到100000时递归深度最坏可能变成链需要用栈模拟或者修改根选择策略但实际比赛里常见数据不会刻意卡递归按常规写法没问题。5.2 几个容易出错的边界细节第一个是“叶子数量m可能不等于叶子判断数量”。有些题目直接把前m个节点规定为叶子但建图后你根据度数判断可能发现某个前m号节点的度数并不是1或者某个非前m号节点度数是1。这通常是因为题目有特殊的编号约定。我建议以题目说明为准而不是完全依赖度数。第二个是“根节点的儿子数量可能为1”。在一棵普通的树上如果你选的根恰好是连接一条长链的端点虽然它原树中度数也可能是1但我们会避免选它当根。如果某个内部非根节点只有一个儿子比如一条长链中间某个度为2的节点它的颜色会完全等于那个儿子。转移中k1lim0自然就处理成dp[u][0]dp[son][0]dp[u][1]dp[son][1]非常合理。第三个是“答案取min还是取固定颜色”。如果你按黑色目标要求做最终输出dp[root][0]而不是min。但很多版本的问法是最少改动几次能让根节点变成黑色由于0和1对称其实计算dp[root][1]也一样只是目标颜色反过来。所以代码里输出min是为了适配“让根节点有一种确定颜色即可”的说法如果你看到原题明确要求黑色请把min改成dp[root][0]。6. 常见问题与排查心得6.1 为什么我把负数全取了答案反而不对这是最常踩的坑。题目允许最多改lim个不是允许把所有收益为负的都改了。举个例子根有三个儿子全0方案里三个儿子都显示0。如果希望根显示0至少需要两个儿子是0也就是最多只能把其中一个改成1。假设三个儿子从0改成1的增量都是-100、-50、-10全部负数看着特别诱人。但如果同时改三个0的数量变成0根就显示成1了直接非法。所以循环里一定要写清楚i lim d0[i] 0。先让数量约束拦住再让符号拦住两个条件缺一不可。6.2 为什么排序之后还要判断小于0不能直接取前lim个如果直接取前lim个会把正的增量也算进去。正的增量代表“把一个0改成1反而要花更多钱”既然全0方案已经合法为什么要花这笔冤枉钱最优方案里正增量的修改必然不会出现。排序后直接从前往后扫遇到负数就加遇到非负数就停才是正确的。6.3 状态定义里到底要不要处理“u本身是叶子却还要往上传”的情况在无根树里叶子就是度数为1的点。选任意非叶节点做根后叶子永远不可能成为其他节点的祖先因此它的DP值不会作为“内部投票”再往下传。但叶子会被爸爸当成一个儿子它的 dp[0] 和 dp[1] 会在爸爸的增量里出现。所以叶子的边界值必须算对否则后面所有父亲节点的贪心都会错。6.4 换根会不会影响答案原题有个漂亮的性质答案与根的选择无关。这也是为什么我们可以随便找一个非叶节点做根而不需要真的把每个根都跑一遍。从直观上看改变根的位置只是重新定义了“父子”的方向而叶子的初始颜色和多数投票规则本质是局部的最终能达成目标所需的最小改动数量不会变。做题时直接利用这个性质省去换根DP。最后分享一个实操技巧我自己刷这题时习惯在草稿纸上先写一个“暴力版本”用背包枚举每个儿子选0还是选1控制0的数量必须过半。这个版本写起来很笨但能帮你确认“平局任选”到底该用哪个数。等暴力结果和贪心结果对拍通过再回来优化成排序贪心。对拍时尤其要覆盖偶数个儿子和只有一个儿子的情况前者考验平局条件后者考验lim0的特殊分支。如果你已经到了能一眼看出“全选0然后改1”的熟练度那这题对你就没有秘密了。真正值得记住的并不是这个贪心本身而是它背后的思考方式面对一个看起来像背包的问题先想想有没有“天然合法方案”再考虑在限制次数内做最小化修正。很多树形DP的转移都是这个套路。