第一次做“叶子的染色”这题时，我把它当成了一道树上的涂色构造题，结果想把“叶子染成什么颜色”直接塞进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数量还会减少，完全没有好处。所以最优方案一定不会改 Δ_i>0 的儿子。
如果一个 Δ_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] 为例，如果k=2，也就是u只有两个儿子，那么只要有一个儿子是0，另一个是1，u的颜色既可以是0也可以是1，因为平局。这时候 need = ceil(2/2) = 1，lim = 1，最多允许改1个0成1。
如果题目改成“多数必须严格”，那么k=2时两个儿子必须都是0，u才能显示0，lim就变成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; vector<int> 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; vector<int> 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和3，2和3都是叶子。假设根不是叶子，儿子2初始颜色0，儿子3初始颜色1，目标让根显示0。
叶子2：dp[2][0]=0，dp[2][1]=1。
叶子3：dp[3][0]=1，dp[3][1]=0。
对于根节点1，k=2，sum0=0+1=1。要把儿子从0改成1的增量分别是：
- 儿子2：1-0=1
- 儿子3：0-1=-1
lim=1，三个增量的排序是[-1, 1]，只取前1个负数，所以 best0=1+(-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)，在n=100000的规模下完全够用。
空间上只需要存图和dp数组，O(n)。如果担心递归栈，n到100000时递归深度最坏可能变成链，需要用栈模拟或者修改根选择策略，但实际比赛里常见数据不会刻意卡递归，按常规写法没问题。
5.2 几个容易出错的边界细节
第一个是“叶子数量m可能不等于叶子判断数量”。有些题目直接把前m个节点规定为叶子，但建图后你根据度数判断可能发现某个前m号节点的度数并不是1，或者某个非前m号节点度数是1。这通常是因为题目有特殊的编号约定。我建议以题目说明为准，而不是完全依赖度数。
第二个是“根节点的儿子数量可能为1”。在一棵普通的树上，如果你选的根恰好是连接一条长链的端点，虽然它原树中度数也可能是1，但我们会避免选它当根。如果某个内部非根节点只有一个儿子，比如一条长链中间某个度为2的节点，它的颜色会完全等于那个儿子。转移中k=1，lim=0，自然就处理成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的数量必须过半。这个版本写起来很笨，但能帮你确认“平局任选”到底该用哪个数。等暴力结果和贪心结果对拍通过，再回来优化成排序贪心。对拍时尤其要覆盖偶数个儿子和只有一个儿子的情况，前者考验平局条件，后者考验lim=0的特殊分支。
如果你已经到了能一眼看出“全选0然后改1”的熟练度，那这题对你就没有秘密了。真正值得记住的并不是这个贪心本身，而是它背后的思考方式：面对一个看起来像背包的问题，先想想有没有“天然合法方案”，再考虑在限制次数内做最小化修正。很多树形DP的转移都是这个套路。
