2023年天梯赛那道L3-2完美树赛后我在补题群里听到最多的抱怨就是明明想到了树形DP怎么一交就T。这题卡人的地方真不在DP思路上而在于你有没有意识到——奇偶性这把刀已经把状态空间砍得只剩巴掌大。你要是还按常规套路开一个宽度为子树大小的背包去卷那必然是O(n²)的复杂度n一旦上到10⁵级别直接原地炸掉。我当时的心理预期也差不多看到树形DP四个字就条件反射地想背包结果被这道题结结实实上了一课。这篇就把我从读题、建模、推转移到写出一个能跑的O(n log n)解法的完整过程摊开讲。关键词先摆在这儿天梯赛、树形DP、完美树、L3_2、01最大/小价值。不管你是刚打完这届天梯赛想复盘还是在准备下一届的L3冲刺或者单纯想搞明白01最大/小价值这种说法到底指什么下面的内容应该都能给你点东西。1. 完美树的约束到底完美在哪1.1 一句差值不超过1锁死了整棵树的形态题目给的约束很短经过任意次改色之后对于树上每一个节点以它为根的子树里两种颜色的节点数量差的绝对值不能超过1。就这么一句话没有一个多余的形容词但它对整棵树施加的是层层嵌套的强约束。关键在于它是对每个节点都成立而不是只看根节点。这意味着你不能只顾着让整棵树平衡还得保证任意一个局部子树都是平衡的。很多人第一反应是那不就是让每个子树尽量平分吗方向没错但尽量这个词太松了。绝对值不超过1意味着差值只能落在-1、0、1三个值上一个都不多。子树节点数如果是偶数那两种颜色的数量必须严格相等差为0没有商量的余地子树节点数如果是奇数差只能是1或者-1二选一。你看约束一写清楚可选空间立刻从一个连续的整数区间塌缩成了最多两个离散取值。这就是这道题第一个反直觉的地方题目看起来是让你去做平衡优化实际上它是在逼你做离散取值的选择。再往深一层想这种嵌套约束还带着一种自下而上的传递性。一个节点的子树是否完美取决于它所有儿子的子树是否完美再加上它自己那一票。你在整棵树的最底层把每棵小子树都调完美了上面一层才有可能完美。这天然就是后序遍历的节奏也是树形DP的典型信号。但请注意不是所有自下而上的题都要套背包这道题就是那个例外。1.2 子树大小的奇偶性才是隐藏的主角我真正想强调的一点是题面里从头到尾没提奇偶两个字但奇偶性才是这题的解题钥匙。你想一棵子树有sz个节点分成两种颜色数量分别是x和yxysz要求|x-y|≤1。那么这个差值|x-y|的奇偶性其实和sz的奇偶性是绑死的。因为x-y x-(sz-x) 2x-sz2x是偶数所以x-y的奇偶性完全由sz决定。于是可以推出一个非常干净的结论子树大小为偶数合法差值只能是0因为2x-sz为偶数且要求落在[-1,1]只有0满足。子树大小为奇数合法差值只能是1或-1因为此时2x-sz为奇数[-1,1]里的奇数只有±1。这个结论直接决定了一棵子树对外能贡献什么。偶数大小的子树对外只有一个姿态不偏不倚差为0奇数大小的子树对外有两个姿态多一个A色或者多一个B色。换句话说一个奇数子树的全部对外信息就是1还是-1这正是关键词里01的味道——每个奇数子树本质上是一个二选一开关。我在补题的时候特意停下来琢磨了一下这个性质越想越觉得精妙。出题人把平衡这个看似连续优化的东西通过取整和绝对值硬生生压成了一个离散二选一问题。你要是没意识到这层就容易写出一个又大又慢的背包一旦意识到了整道题的结构瞬间清爽。1.3 为什么这题不适合无脑开大数组的树形背包顺着常规思路你会很自然地定义dp[u][delta]delta表示子树u内两种颜色的数量差。问题来了delta的取值范围是多少如果你不做任何剪枝delta可以取到[-sz[u], sz[u]]里的所有值那这就是一个标准的树形背包合并两个子树是两个数组的卷积复杂度是O(n²)。但这个范围其实是虚的。因为子树u自己这一层的约束要求|delta|≤1而delta又由子节点的贡献加和而来。也就是说你辛辛苦苦枚举的绝大多数delta值最终都因为不满足|delta|≤1被丢弃了。既然如此为什么不一开始就把范围掐死在{-1,0,1}呢答案是可以的但前提是你要处理好中间过程可能短暂超出范围的情况——加一个大正数再加一个大负数最后可能回到[-1,1]。这个细节我在第3节会掰开讲。总之结论是这题的最优解不是背包卷积而是一次排序加前缀和时间复杂度直接降到O(n log n)甚至O(n)。2. dp状态怎么定三种差值一个节点2.1 单点改色代价的建模方式先把题目的输入模型固定下来。每个节点i有一个初始颜色c_i以及把它最终定成颜色0的代价cost0[i]、定成颜色1的代价cost1[i]。这里的代价含义是不管你原来是啥色只要最终变成目标色就付对应的钱。这么建模的好处是它足够通用——如果题目给的是翻转一次花x那你也能换算成保持原色花0、翻成另一色花x。基于这个模型单个节点的选择其实就两种最终定成0付cost0[i]最终定成1付cost1[i]。节点自己对子树的差值贡献是多少如果它定成0那它对颜色0的个数减颜色1的个数这个差值的贡献就是1定成1就是-1。我们把节点自己的贡献记成w定成0时w1定成1时w-1。就这么简单一个节点全部的信息就是选0还是选1以及各自多少钱又是二选一。到这里你会发现整道题从根到叶处处是二选一。节点自己二选一奇数子树对外二选一偶数子树干脆没得选。这种处处是开关的结构正是01最大/小价值这个关键词的来源——我们要做的就是在这些开关里挑出总代价最小的那套组合。2.2 子节点能给出的贡献只有0或±1现在看一个节点u它有若干个子节点v。每个子节点v自己也是一棵完美的子树它能给u贡献一个差值d_v。根据第1节的结论如果sz[v]是偶数那么d_v只能是0这个子节点在差值这件事上就是个哑巴它不改变总的差值但它有自己的代价dp0[v]。如果sz[v]是奇数那么d_v只能是1或者-1对应代价分别记作dp1[v]和dpm1[v]。我们定义三个值来描述子树vdp0[v]表示v子树完美且差值为0的最小代价dp1[v]表示差值为1dpm1[v]表示差值为-1。对于偶数子树只有dp0[v]有意义对于奇数子树只有dp1[v]和dpm1[v]有意义。你甚至可以认为无效的那些状态是无穷大这样统一处理起来更省心。这一步是整个建模的核心。它把每个子节点压缩成了一个要么0、要么在±1里挑一个的贡献单元。想想看一棵可能有几万个节点的子树对外居然只用一个三值状态就能概括这种信息压缩正是解这道题的爽点所在。你要是没做这层压缩dp数组的维度就会失控。2.3 转移方程的完整推导把节点u的所有子节点贡献加起来再加上u自己的贡献w就得到u子树的总差值delta w Σ d_v约束要求最终|delta|≤1。同时u子树的节点数是sz[u] 1 Σ sz[v]所以delta的奇偶性也被sz[u]锁死sz[u]为偶数则delta0为奇数则delta±1。这两个条件要同时满足缺一不可。统计一下假设u有m个奇数大小的子节点其余是偶数子节点。偶数子节点贡献固定为0只贡献代价m个奇数子节点每个选1或-1。设其中有p个选了1那么就有(m-p)个选了-1于是Σd_v p - (m-p) 2p - m。代进delta的表达式delta w 2p - m我们要让这个值落在允许的集合里。给定w由u选0还是选1决定和m每个合法的delta都反推出一个唯一确定的pp (delta - w m) / 2注意这里p必须是[0,m]之间的整数否则这个delta对这个颜色的选择就是不可达的。整个转移就变成了对每种合法组合算出一个必须恰好选p个子节点取1的方案然后求最小代价。你看一堆看起来复杂的组合被约束一逼就只剩选几个这一个自由度了。3. 01最大/小价值合并时的贪心选法3.1 把选哪些子树取1变成一个排序问题现在问题被彻底简化成一个组合优化小问题有m个奇数子节点每个子节点v如果取-1代价是dpm1[v]如果取1代价是dp1[v]。现在要求恰好选p个取1怎么选总代价最小做法非常朴素先假设全取-1总代价base Σ dpm1[v]这一定是可行的基线。然后定义每个子节点从-1切换到1的增量delta_v dp1[v] - dpm1[v]这个增量可能为正切过去更贵也可能为负切过去更便宜说明这棵子树本身就更倾向于1。要恰好切p个过去我们当然希望总增量最小所以把所有的delta_v排个序取最小的p个加起来再叠到base上。这就是最优方案。这里要提醒一个容易被忽略的点即使某些delta_v是正数只要p大于负增量的个数你也必须捏着鼻子去切那些正增量的子树因为你没有选择——p是约束定死的不是随便挑。很多人初学时总想着只切负的、正的不切但那会导致实际取1的个数不足p最终delta不满足约束答案是错的。3.2 为什么取最小的p个增量就是最优有人可能会问取最小的p个delta凭什么保证最优理由其实很直接。总代价可以写成总代价 base Σ(被选中切换的delta_v)base是定死的所以要最小化总代价等价于最小化被选中切换的那p个delta_v之和。在m个增量里选p个使其和最小当然就是排序后取最小的那p个。这是一个无争议的贪心不需要什么证明技巧。不过这里藏着一个小陷阱我要专门点一下如果你为每个节点枚举所有可能的delta0、1、-1然后想用背包去卷那你就又掉回大数组的老路了。正确地利用p唯一确定这个性质才是把复杂度降下来的关键。每个节点u在固定颜色w和固定目标delta之后p是唯一的所以你根本不需要背包只需要一次排序加一次前缀和。子节点之间是相互独立的它们的delta_v互不影响排序贪心完全成立。3.3 复杂度从O(n²)降到O(n log n)来算一笔账。对每个节点u我们要对它的所有奇数子节点做一次排序。一个节点u的排序规模是它的奇数子节点个数m_u。所有节点加起来Σm_u不会超过节点的总数每个节点最多作为某个父节点的一个子节点被统计一次所以总的排序元素个数是O(n)。即使每个子树单独排序总复杂度也就是O(n log n)——而且还不是那种最坏情况的n log n实际跑起来很快因为每个节点的m_u通常很小。对比一下朴素背包每个节点合并子节点时数组长度是子树大小量级父节点合并多个子节点会有卷积开销总的复杂度是O(n²)n10⁵时是10¹⁰量级的操作稳稳超时。这就是为什么我说这题的关键不在树形DP本身而在于你有没有把状态空间压干净。压对了O(n log n)轻松过压错了再好的常数也救不回来。还有一个可以进一步优化的点其实你根本不需要对每个节点完整排序因为你要的是最小的p个delta之和。如果m_u很小直接排就行如果m_u很大可以用std::nth_element找出第p小再求和理论上能到O(m_u)。不过实测下来排序的常数开销更友好除非你被卡到极限否则std::sort完全够用。提示增量数组里可能出现两个子树增量相等的情况这没关系排序稳定与否不影响最终求和结果取最小的p个值即可。4. 代码落地与实现细节4.1 建图与后序遍历先把树的存储结构确定下来。既然是给一棵以1为根的有根树邻接表建无向图然后从根做一次DFS即可。需要注意n在1e5甚至更大时递归DFS有爆栈风险稳妥做法是写一个迭代版的后序遍历或者手动开栈、加大系统栈。我个人的习惯是n不超过2×10⁵时直接递归用编译器的栈扩容参数兜底再大就写迭代版本从根开始做一次BFS得到遍历序再逆序处理天然就是后序。后序遍历的顺序至关重要因为节点u的转移依赖所有子节点的dp值。逆BFS序从叶子往根是等价于后序的而且实现简洁不涉及递归。我下面给的代码用递归写法逻辑更直观你在实际提交时按自己的习惯改迭代即可。另外一个细节代价可能很大题目如果给的是1e9量级的代价n又是1e5总和可能到1e14必须用64位整数。我见过不止一个人在这题上写int然后WA到怀疑人生检查半天逻辑最后发现是溢出。4.2 dp数组的初始化与合并顺序dp数组的定义dp0[u]、dp1[u]、dpm1[u]分别表示u子树完美且总差值为0、1、-1的最小代价。初始化时全部设为无穷大然后枚举u最终的颜色。对每个颜色col0或1基础代价c cost_col[u]w (col0 ? 1 : -1)。然后收集所有的奇数子节点v把dpm1[v]累进base把dp1[v]-dpm1[v]放进增量数组偶数子节点直接把dp0[v]累进base。接着对增量数组排序、前缀和。然后枚举目标差值delta ∈ {-1,0,1}用公式p (delta - w m)/2反推p检查p是否在[0,m]内且为整数若是则用base prefix[p]更新对应状态。这里一定要记得检查整除和边界p算出个负数或者小数说明这个delta对这组cnadidate不可达直接跳过。合并顺序上没什么讲究因为子节点之间独立先合并谁后合并谁无所谓。但要注意在枚举颜色和delta时同一个目标状态可能被两种颜色同时更新到取min即可。4.3 完整代码与逐段说明下面这份代码可以直接作为模板参考注释我写得比较细方便你对照前面的推导看#include bits/stdc.h using namespace std; const long long INF (long long)4e18; int n; vectorvectorint g; vectorlong long cost0, cost1; // 定成0/1的代价 vectorlong long dp0, dp1, dpm1; // 三种差值状态 vectorint sz; void dfs(int u, int p) { sz[u] 1; long long base 0; vectorlong long delta; for (int v : g[u]) { if (v p) continue; dfs(v, u); sz[u] sz[v]; } // 子树大小已经算好开始收集贡献 for (int v : g[u]) { if (v p) continue; if (sz[v] % 2 0) { base dp0[v]; // 偶数子树贡献固定为0 } else { base dpm1[v]; // 先默认全取 -1 delta.push_back(dp1[v] - dpm1[v]); } } sort(delta.begin(), delta.end()); int m (int)delta.size(); vectorlong long pre(m 1, 0); for (int i 0; i m; i) pre[i 1] pre[i] delta[i]; dp0[u] dp1[u] dpm1[u] INF; for (int col 0; col 1; col) { long long c (col 0 ? cost0[u] : cost1[u]); int w (col 0 ? 1 : -1); for (int d -1; d 1; d) { int num d - w m; // num 2p if (num 0 || num 2 * m) continue; if (num % 2 ! 0) continue; int p num / 2; // 恰好取 p 个 1 long long val c base pre[p]; if (d 0) dp0[u] min(dp0[u], val); else if (d 1) dp1[u] min(dp1[u], val); else dpm1[u] min(dpm1[u], val); } } } int main() { scanf(%d, n); g.assign(n 1, {}); cost0.assign(n 1, 0); cost1.assign(n 1, 0); dp0.assign(n 1, INF); dp1.assign(n 1, INF); dpm1.assign(n 1, INF); sz.assign(n 1, 0); // 读入每个点的两种代价按题目实际格式调整 for (int i 1; i n; i) scanf(%lld %lld, cost0[i], cost1[i]); // 读入 n-1 条边 for (int i 1; i n; i) { int u, v; scanf(%d %d, u, v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); long long ans; if (n % 2 0) ans dp0[1]; else ans min(dp1[1], dpm1[1]); printf(%lld\n, ans); return 0; }几个一定要盯紧的地方。第一递归DFS在n很大时可能爆栈稳妥改迭代。第二读入代价的格式一定要按题目来有的题给的是改色代价有的给的是初始色 花费别想当然。第三ans的选择要按n的奇偶性来偶数n根节点差值必须为0奇数n取±1里较小的。第四INF别设太小4e18是个安全值但如果你用INF做加法记得防溢出我上面是先把base算好再加c没直接加INF这点要留意。5. 对拍、卡常与赛时踩坑记录5.1 几个写反就全错的细节这题有几处特别容易写反或者漏掉。首先是w的符号定成颜色0时w1还是-1这取决于你delta的定义。我前面定义delta是颜色0的数量减去颜色1的数量所以定成0贡献1。如果你的定义反了那w、dp1、dpm1的语义全都要跟着翻极容易出bug。写代码前先在纸上把定义写死别中途改。其次是增量数组存的是dp1[v]-dpm1[v]别写成dpm1[v]-dp1[v]。如果你写反了排序取最小的p个会选出完全相反的方案答案直接错。验证方法拿一个只有两个节点的树手算两个叶子都是奇数子树看看取1和取-1分别对应什么。再一个是p的范围检查。num d - w m必须落在[0, 2m]且为偶数。有些人只检查了p≥0忘了p≤m结果数组越界或者取到错误的p。这个检查是必须的不是可选的。最后是dp数组的初始化时机。我们是在节点u的所有子节点处理完之后才初始化dp0[u]等为INF的然后才枚举颜色更新。如果你提前初始化又中途被覆盖就会丢解。5.2 用暴力对拍验证的正确姿势这道题的约束比较特殊光靠样例很难覆盖所有情况。我推荐写一个暴力版本对拍对每个节点把它最终颜色当成变量0或1枚举所有2ⁿ种染色方案检查是否满足每个子树差值不超过1并计算代价取最小。n取到10左右就能跑虽然是指数级但对拍够用了。对拍流程随机生成n比如8到12、随机生成树结构、随机生成代价然后跑你的正解和暴力比较结果。我大概跑了500组才敢放心提交的正解。这里有个经验随机生成树的时候别总用随机父节点那种那样生成的树太扁要混合生成链、菊花、随机树三种形态才能覆盖到不同奇偶分布因为这道题对树形结构非常敏感。5.3 特殊形态单链、菊花、n1单链是最容易暴露奇偶性bug的形态。一条长度为n的链每一层子树的奇偶性交替变化你的状态切换逻辑如果有一点问题单链上就会立刻出错。建议手动构造n1、2、3、4的链逐个手算验证。菊花图根连着一堆叶子也值得测。此时根的子节点全是叶子每个都是奇数子树m就等于叶子数转移里恰好选p个取1的作用会被放大到极致能有效检验你的贪心选法。n1的情况更别漏此时根就是叶子没有子节点m0delta只能是w±1答案就是min(cost0[1], cost1[1])。我见过有人在这种边界上因为数组下标或者循环写的直接RE。最后分享一个我自己踩过的坑优化的时候我一度想省掉排序直接用所有负增量必选、正增量按需补结果发现当p小于负增量个数时也没问题但当p大于负增量个数时逻辑就变得很绕容易越写越乱。老老实实排序取前p个几十行代码清清楚楚何必跟自己较劲。这道完美树绕了一大圈最后落在排序取最小的p个这么一个朴素的结论上反倒让我觉得——约束越强、状态越少题目反而越优雅。
天梯赛L3-2完美树：树形DP奇偶性与01价值贪心优化
2023年天梯赛那道L3-2完美树赛后我在补题群里听到最多的抱怨就是明明想到了树形DP怎么一交就T。这题卡人的地方真不在DP思路上而在于你有没有意识到——奇偶性这把刀已经把状态空间砍得只剩巴掌大。你要是还按常规套路开一个宽度为子树大小的背包去卷那必然是O(n²)的复杂度n一旦上到10⁵级别直接原地炸掉。我当时的心理预期也差不多看到树形DP四个字就条件反射地想背包结果被这道题结结实实上了一课。这篇就把我从读题、建模、推转移到写出一个能跑的O(n log n)解法的完整过程摊开讲。关键词先摆在这儿天梯赛、树形DP、完美树、L3_2、01最大/小价值。不管你是刚打完这届天梯赛想复盘还是在准备下一届的L3冲刺或者单纯想搞明白01最大/小价值这种说法到底指什么下面的内容应该都能给你点东西。1. 完美树的约束到底完美在哪1.1 一句差值不超过1锁死了整棵树的形态题目给的约束很短经过任意次改色之后对于树上每一个节点以它为根的子树里两种颜色的节点数量差的绝对值不能超过1。就这么一句话没有一个多余的形容词但它对整棵树施加的是层层嵌套的强约束。关键在于它是对每个节点都成立而不是只看根节点。这意味着你不能只顾着让整棵树平衡还得保证任意一个局部子树都是平衡的。很多人第一反应是那不就是让每个子树尽量平分吗方向没错但尽量这个词太松了。绝对值不超过1意味着差值只能落在-1、0、1三个值上一个都不多。子树节点数如果是偶数那两种颜色的数量必须严格相等差为0没有商量的余地子树节点数如果是奇数差只能是1或者-1二选一。你看约束一写清楚可选空间立刻从一个连续的整数区间塌缩成了最多两个离散取值。这就是这道题第一个反直觉的地方题目看起来是让你去做平衡优化实际上它是在逼你做离散取值的选择。再往深一层想这种嵌套约束还带着一种自下而上的传递性。一个节点的子树是否完美取决于它所有儿子的子树是否完美再加上它自己那一票。你在整棵树的最底层把每棵小子树都调完美了上面一层才有可能完美。这天然就是后序遍历的节奏也是树形DP的典型信号。但请注意不是所有自下而上的题都要套背包这道题就是那个例外。1.2 子树大小的奇偶性才是隐藏的主角我真正想强调的一点是题面里从头到尾没提奇偶两个字但奇偶性才是这题的解题钥匙。你想一棵子树有sz个节点分成两种颜色数量分别是x和yxysz要求|x-y|≤1。那么这个差值|x-y|的奇偶性其实和sz的奇偶性是绑死的。因为x-y x-(sz-x) 2x-sz2x是偶数所以x-y的奇偶性完全由sz决定。于是可以推出一个非常干净的结论子树大小为偶数合法差值只能是0因为2x-sz为偶数且要求落在[-1,1]只有0满足。子树大小为奇数合法差值只能是1或-1因为此时2x-sz为奇数[-1,1]里的奇数只有±1。这个结论直接决定了一棵子树对外能贡献什么。偶数大小的子树对外只有一个姿态不偏不倚差为0奇数大小的子树对外有两个姿态多一个A色或者多一个B色。换句话说一个奇数子树的全部对外信息就是1还是-1这正是关键词里01的味道——每个奇数子树本质上是一个二选一开关。我在补题的时候特意停下来琢磨了一下这个性质越想越觉得精妙。出题人把平衡这个看似连续优化的东西通过取整和绝对值硬生生压成了一个离散二选一问题。你要是没意识到这层就容易写出一个又大又慢的背包一旦意识到了整道题的结构瞬间清爽。1.3 为什么这题不适合无脑开大数组的树形背包顺着常规思路你会很自然地定义dp[u][delta]delta表示子树u内两种颜色的数量差。问题来了delta的取值范围是多少如果你不做任何剪枝delta可以取到[-sz[u], sz[u]]里的所有值那这就是一个标准的树形背包合并两个子树是两个数组的卷积复杂度是O(n²)。但这个范围其实是虚的。因为子树u自己这一层的约束要求|delta|≤1而delta又由子节点的贡献加和而来。也就是说你辛辛苦苦枚举的绝大多数delta值最终都因为不满足|delta|≤1被丢弃了。既然如此为什么不一开始就把范围掐死在{-1,0,1}呢答案是可以的但前提是你要处理好中间过程可能短暂超出范围的情况——加一个大正数再加一个大负数最后可能回到[-1,1]。这个细节我在第3节会掰开讲。总之结论是这题的最优解不是背包卷积而是一次排序加前缀和时间复杂度直接降到O(n log n)甚至O(n)。2. dp状态怎么定三种差值一个节点2.1 单点改色代价的建模方式先把题目的输入模型固定下来。每个节点i有一个初始颜色c_i以及把它最终定成颜色0的代价cost0[i]、定成颜色1的代价cost1[i]。这里的代价含义是不管你原来是啥色只要最终变成目标色就付对应的钱。这么建模的好处是它足够通用——如果题目给的是翻转一次花x那你也能换算成保持原色花0、翻成另一色花x。基于这个模型单个节点的选择其实就两种最终定成0付cost0[i]最终定成1付cost1[i]。节点自己对子树的差值贡献是多少如果它定成0那它对颜色0的个数减颜色1的个数这个差值的贡献就是1定成1就是-1。我们把节点自己的贡献记成w定成0时w1定成1时w-1。就这么简单一个节点全部的信息就是选0还是选1以及各自多少钱又是二选一。到这里你会发现整道题从根到叶处处是二选一。节点自己二选一奇数子树对外二选一偶数子树干脆没得选。这种处处是开关的结构正是01最大/小价值这个关键词的来源——我们要做的就是在这些开关里挑出总代价最小的那套组合。2.2 子节点能给出的贡献只有0或±1现在看一个节点u它有若干个子节点v。每个子节点v自己也是一棵完美的子树它能给u贡献一个差值d_v。根据第1节的结论如果sz[v]是偶数那么d_v只能是0这个子节点在差值这件事上就是个哑巴它不改变总的差值但它有自己的代价dp0[v]。如果sz[v]是奇数那么d_v只能是1或者-1对应代价分别记作dp1[v]和dpm1[v]。我们定义三个值来描述子树vdp0[v]表示v子树完美且差值为0的最小代价dp1[v]表示差值为1dpm1[v]表示差值为-1。对于偶数子树只有dp0[v]有意义对于奇数子树只有dp1[v]和dpm1[v]有意义。你甚至可以认为无效的那些状态是无穷大这样统一处理起来更省心。这一步是整个建模的核心。它把每个子节点压缩成了一个要么0、要么在±1里挑一个的贡献单元。想想看一棵可能有几万个节点的子树对外居然只用一个三值状态就能概括这种信息压缩正是解这道题的爽点所在。你要是没做这层压缩dp数组的维度就会失控。2.3 转移方程的完整推导把节点u的所有子节点贡献加起来再加上u自己的贡献w就得到u子树的总差值delta w Σ d_v约束要求最终|delta|≤1。同时u子树的节点数是sz[u] 1 Σ sz[v]所以delta的奇偶性也被sz[u]锁死sz[u]为偶数则delta0为奇数则delta±1。这两个条件要同时满足缺一不可。统计一下假设u有m个奇数大小的子节点其余是偶数子节点。偶数子节点贡献固定为0只贡献代价m个奇数子节点每个选1或-1。设其中有p个选了1那么就有(m-p)个选了-1于是Σd_v p - (m-p) 2p - m。代进delta的表达式delta w 2p - m我们要让这个值落在允许的集合里。给定w由u选0还是选1决定和m每个合法的delta都反推出一个唯一确定的pp (delta - w m) / 2注意这里p必须是[0,m]之间的整数否则这个delta对这个颜色的选择就是不可达的。整个转移就变成了对每种合法组合算出一个必须恰好选p个子节点取1的方案然后求最小代价。你看一堆看起来复杂的组合被约束一逼就只剩选几个这一个自由度了。3. 01最大/小价值合并时的贪心选法3.1 把选哪些子树取1变成一个排序问题现在问题被彻底简化成一个组合优化小问题有m个奇数子节点每个子节点v如果取-1代价是dpm1[v]如果取1代价是dp1[v]。现在要求恰好选p个取1怎么选总代价最小做法非常朴素先假设全取-1总代价base Σ dpm1[v]这一定是可行的基线。然后定义每个子节点从-1切换到1的增量delta_v dp1[v] - dpm1[v]这个增量可能为正切过去更贵也可能为负切过去更便宜说明这棵子树本身就更倾向于1。要恰好切p个过去我们当然希望总增量最小所以把所有的delta_v排个序取最小的p个加起来再叠到base上。这就是最优方案。这里要提醒一个容易被忽略的点即使某些delta_v是正数只要p大于负增量的个数你也必须捏着鼻子去切那些正增量的子树因为你没有选择——p是约束定死的不是随便挑。很多人初学时总想着只切负的、正的不切但那会导致实际取1的个数不足p最终delta不满足约束答案是错的。3.2 为什么取最小的p个增量就是最优有人可能会问取最小的p个delta凭什么保证最优理由其实很直接。总代价可以写成总代价 base Σ(被选中切换的delta_v)base是定死的所以要最小化总代价等价于最小化被选中切换的那p个delta_v之和。在m个增量里选p个使其和最小当然就是排序后取最小的那p个。这是一个无争议的贪心不需要什么证明技巧。不过这里藏着一个小陷阱我要专门点一下如果你为每个节点枚举所有可能的delta0、1、-1然后想用背包去卷那你就又掉回大数组的老路了。正确地利用p唯一确定这个性质才是把复杂度降下来的关键。每个节点u在固定颜色w和固定目标delta之后p是唯一的所以你根本不需要背包只需要一次排序加一次前缀和。子节点之间是相互独立的它们的delta_v互不影响排序贪心完全成立。3.3 复杂度从O(n²)降到O(n log n)来算一笔账。对每个节点u我们要对它的所有奇数子节点做一次排序。一个节点u的排序规模是它的奇数子节点个数m_u。所有节点加起来Σm_u不会超过节点的总数每个节点最多作为某个父节点的一个子节点被统计一次所以总的排序元素个数是O(n)。即使每个子树单独排序总复杂度也就是O(n log n)——而且还不是那种最坏情况的n log n实际跑起来很快因为每个节点的m_u通常很小。对比一下朴素背包每个节点合并子节点时数组长度是子树大小量级父节点合并多个子节点会有卷积开销总的复杂度是O(n²)n10⁵时是10¹⁰量级的操作稳稳超时。这就是为什么我说这题的关键不在树形DP本身而在于你有没有把状态空间压干净。压对了O(n log n)轻松过压错了再好的常数也救不回来。还有一个可以进一步优化的点其实你根本不需要对每个节点完整排序因为你要的是最小的p个delta之和。如果m_u很小直接排就行如果m_u很大可以用std::nth_element找出第p小再求和理论上能到O(m_u)。不过实测下来排序的常数开销更友好除非你被卡到极限否则std::sort完全够用。提示增量数组里可能出现两个子树增量相等的情况这没关系排序稳定与否不影响最终求和结果取最小的p个值即可。4. 代码落地与实现细节4.1 建图与后序遍历先把树的存储结构确定下来。既然是给一棵以1为根的有根树邻接表建无向图然后从根做一次DFS即可。需要注意n在1e5甚至更大时递归DFS有爆栈风险稳妥做法是写一个迭代版的后序遍历或者手动开栈、加大系统栈。我个人的习惯是n不超过2×10⁵时直接递归用编译器的栈扩容参数兜底再大就写迭代版本从根开始做一次BFS得到遍历序再逆序处理天然就是后序。后序遍历的顺序至关重要因为节点u的转移依赖所有子节点的dp值。逆BFS序从叶子往根是等价于后序的而且实现简洁不涉及递归。我下面给的代码用递归写法逻辑更直观你在实际提交时按自己的习惯改迭代即可。另外一个细节代价可能很大题目如果给的是1e9量级的代价n又是1e5总和可能到1e14必须用64位整数。我见过不止一个人在这题上写int然后WA到怀疑人生检查半天逻辑最后发现是溢出。4.2 dp数组的初始化与合并顺序dp数组的定义dp0[u]、dp1[u]、dpm1[u]分别表示u子树完美且总差值为0、1、-1的最小代价。初始化时全部设为无穷大然后枚举u最终的颜色。对每个颜色col0或1基础代价c cost_col[u]w (col0 ? 1 : -1)。然后收集所有的奇数子节点v把dpm1[v]累进base把dp1[v]-dpm1[v]放进增量数组偶数子节点直接把dp0[v]累进base。接着对增量数组排序、前缀和。然后枚举目标差值delta ∈ {-1,0,1}用公式p (delta - w m)/2反推p检查p是否在[0,m]内且为整数若是则用base prefix[p]更新对应状态。这里一定要记得检查整除和边界p算出个负数或者小数说明这个delta对这组cnadidate不可达直接跳过。合并顺序上没什么讲究因为子节点之间独立先合并谁后合并谁无所谓。但要注意在枚举颜色和delta时同一个目标状态可能被两种颜色同时更新到取min即可。4.3 完整代码与逐段说明下面这份代码可以直接作为模板参考注释我写得比较细方便你对照前面的推导看#include bits/stdc.h using namespace std; const long long INF (long long)4e18; int n; vectorvectorint g; vectorlong long cost0, cost1; // 定成0/1的代价 vectorlong long dp0, dp1, dpm1; // 三种差值状态 vectorint sz; void dfs(int u, int p) { sz[u] 1; long long base 0; vectorlong long delta; for (int v : g[u]) { if (v p) continue; dfs(v, u); sz[u] sz[v]; } // 子树大小已经算好开始收集贡献 for (int v : g[u]) { if (v p) continue; if (sz[v] % 2 0) { base dp0[v]; // 偶数子树贡献固定为0 } else { base dpm1[v]; // 先默认全取 -1 delta.push_back(dp1[v] - dpm1[v]); } } sort(delta.begin(), delta.end()); int m (int)delta.size(); vectorlong long pre(m 1, 0); for (int i 0; i m; i) pre[i 1] pre[i] delta[i]; dp0[u] dp1[u] dpm1[u] INF; for (int col 0; col 1; col) { long long c (col 0 ? cost0[u] : cost1[u]); int w (col 0 ? 1 : -1); for (int d -1; d 1; d) { int num d - w m; // num 2p if (num 0 || num 2 * m) continue; if (num % 2 ! 0) continue; int p num / 2; // 恰好取 p 个 1 long long val c base pre[p]; if (d 0) dp0[u] min(dp0[u], val); else if (d 1) dp1[u] min(dp1[u], val); else dpm1[u] min(dpm1[u], val); } } } int main() { scanf(%d, n); g.assign(n 1, {}); cost0.assign(n 1, 0); cost1.assign(n 1, 0); dp0.assign(n 1, INF); dp1.assign(n 1, INF); dpm1.assign(n 1, INF); sz.assign(n 1, 0); // 读入每个点的两种代价按题目实际格式调整 for (int i 1; i n; i) scanf(%lld %lld, cost0[i], cost1[i]); // 读入 n-1 条边 for (int i 1; i n; i) { int u, v; scanf(%d %d, u, v); g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); long long ans; if (n % 2 0) ans dp0[1]; else ans min(dp1[1], dpm1[1]); printf(%lld\n, ans); return 0; }几个一定要盯紧的地方。第一递归DFS在n很大时可能爆栈稳妥改迭代。第二读入代价的格式一定要按题目来有的题给的是改色代价有的给的是初始色 花费别想当然。第三ans的选择要按n的奇偶性来偶数n根节点差值必须为0奇数n取±1里较小的。第四INF别设太小4e18是个安全值但如果你用INF做加法记得防溢出我上面是先把base算好再加c没直接加INF这点要留意。5. 对拍、卡常与赛时踩坑记录5.1 几个写反就全错的细节这题有几处特别容易写反或者漏掉。首先是w的符号定成颜色0时w1还是-1这取决于你delta的定义。我前面定义delta是颜色0的数量减去颜色1的数量所以定成0贡献1。如果你的定义反了那w、dp1、dpm1的语义全都要跟着翻极容易出bug。写代码前先在纸上把定义写死别中途改。其次是增量数组存的是dp1[v]-dpm1[v]别写成dpm1[v]-dp1[v]。如果你写反了排序取最小的p个会选出完全相反的方案答案直接错。验证方法拿一个只有两个节点的树手算两个叶子都是奇数子树看看取1和取-1分别对应什么。再一个是p的范围检查。num d - w m必须落在[0, 2m]且为偶数。有些人只检查了p≥0忘了p≤m结果数组越界或者取到错误的p。这个检查是必须的不是可选的。最后是dp数组的初始化时机。我们是在节点u的所有子节点处理完之后才初始化dp0[u]等为INF的然后才枚举颜色更新。如果你提前初始化又中途被覆盖就会丢解。5.2 用暴力对拍验证的正确姿势这道题的约束比较特殊光靠样例很难覆盖所有情况。我推荐写一个暴力版本对拍对每个节点把它最终颜色当成变量0或1枚举所有2ⁿ种染色方案检查是否满足每个子树差值不超过1并计算代价取最小。n取到10左右就能跑虽然是指数级但对拍够用了。对拍流程随机生成n比如8到12、随机生成树结构、随机生成代价然后跑你的正解和暴力比较结果。我大概跑了500组才敢放心提交的正解。这里有个经验随机生成树的时候别总用随机父节点那种那样生成的树太扁要混合生成链、菊花、随机树三种形态才能覆盖到不同奇偶分布因为这道题对树形结构非常敏感。5.3 特殊形态单链、菊花、n1单链是最容易暴露奇偶性bug的形态。一条长度为n的链每一层子树的奇偶性交替变化你的状态切换逻辑如果有一点问题单链上就会立刻出错。建议手动构造n1、2、3、4的链逐个手算验证。菊花图根连着一堆叶子也值得测。此时根的子节点全是叶子每个都是奇数子树m就等于叶子数转移里恰好选p个取1的作用会被放大到极致能有效检验你的贪心选法。n1的情况更别漏此时根就是叶子没有子节点m0delta只能是w±1答案就是min(cost0[1], cost1[1])。我见过有人在这种边界上因为数组下标或者循环写的直接RE。最后分享一个我自己踩过的坑优化的时候我一度想省掉排序直接用所有负增量必选、正增量按需补结果发现当p小于负增量个数时也没问题但当p大于负增量个数时逻辑就变得很绕容易越写越乱。老老实实排序取前p个几十行代码清清楚楚何必跟自己较劲。这道完美树绕了一大圈最后落在排序取最小的p个这么一个朴素的结论上反倒让我觉得——约束越强、状态越少题目反而越优雅。