整整一届天梯赛打完群里讨论最热的往往不是最后的压轴而是那种名字唬人、读完有思路、下笔全是坑的题。2023 年这道 L3_2完美树就属于典型刚看标题以为要搞什么高深的树论读题之后发现是一棵普普通通的树、每个点只有 0 和 1 两种状态但真要写对涉及建树、状态统计、无解判定一步错就全盘挂。赛后我把它从头到尾重写了一遍也翻了不少人的思路才把树形DP和01最大/小价值这两个标签背后的东西对上号。这篇就把这道题完整拆一遍从题意到推导再到可复制的代码顺带聊聊几个容易翻车的地方。刚学树形DP、想找一道能上手的中等难度题的人或者打过几场天梯赛、想看看自己思路差在哪的人应该都能捡到东西。1. 先把题目嚼碎这道完美树到底在问什么1.1 一句话说清题意给你一棵有 n 个节点的树每个节点染成黑或白也就是数值 0 或 1。你可以在树上删掉若干条边删完之后整棵树就碎成了若干个连通块。约束是每一个连通块里值为 0 的节点个数必须和值为 1 的节点个数一模一样这种块我后面统一叫完美块。问题来了最多能把整棵树切成多少个完美块如果怎么切都做不到输出 -1。这里有个细节容易被忽略题目问的是最多。为什么不能问最少因为在树上不切边本身就是一种合法方案如果整棵树的黑白数量本来就相等那最少就是 1 块切 0 条边问题瞬间变得没意义。所以出题人只能往最多这个方向问逼着你去思考什么时候可以果断下刀。还有一个等价的说法值得一提在一棵树上切出 k 个连通块恰好要删掉 k-1 条边所以最多块数和最多删边数是同一件事很多版本干脆把它写成最多能删多少条边本质没有任何区别算出来的块数减 1 就是边数。理解到这一层这道题的骨架就清楚了它是一个在树上做划分、且划分条件跟数量平衡挂钩的优化问题。1.2 为什么它挂着树形DP的名号看到树上划分最优块数第一反应应该就是树形DP。因为树天然有递归结构一个节点的答案往往能由它的儿子节点的答案拼出来。这道题也一样主流的解法就是自底向上跑一遍 DFS每个节点维护我这一坨子树内部能切出几块以及我这一坨子树还欠账多少两个信息合起来往外传。不过我得说句实在话这道题的树形DP味道其实比较淡它更像是披着DP皮的贪心。真正写起来很多人的代码里连 dp 数组都没有只用一个子树黑白差值就跑完了。那为什么题解圈还是习惯把它归到树形DP因为它考察的核心能力——在树上定义一个可以自底向上合并的状态并证明合并方式最优——这正是树形DP的内核。你把它当成DP来想思路会顺很多把它当成纯贪心也照样能过但证明为什么贪心是对的这一步省不掉。1.3 01最大/小价值到底指什么这个词有点绕我拆开讲。它其实指的是题目里每个节点的状态只有两种0 或者 1。在处理的时候我们习惯把它们折算成带符号的价值——比如把 0 记为 1把 1 记为 -1那么一个连通块是不是完美的就等价于它内部价值之和是不是 0。这么一转化黑白数量相等这个看起来很具体的条件就变成了一个纯粹的求和问题子树价值之和等于 0就是完美块。另一种理解是把每个子树的切或者不切当成一个 01 决策切了价值 1多一块不切价值 0求价值最大。两种理解其实是同一件事的两面一个盯着节点价值一个盯着决策价值。题目标签里的01最大/小价值说的就是这套把离散状态折算成可累加价值的思路。想通这一层后面的推导就水到渠成了。2. 思路主线把颜色折算成价值让子树自己开口说话2.1 从数颜色到算差值我一开始的思路特别朴素对每个子树我分别数 0 有几个、1 有几个然后比大小。这样当然能做但会带来一个麻烦——你需要同时维护两个计数还要在合并的时候分别累加代码啰嗦且容易写错。改成价值法之后就干净多了给每个节点定一个权重0 记 11 记 -1那么子树的价值就是它内部所有节点的权重之和。设val[u]表示以 u 为根的子树的价值和。这个值有个非常直观的含义它等于子树里 0 的个数减去 1 的个数。所以val[u] 0这块里 0 比 1 多欠着 1val[u] 0这块里 1 比 0 多欠着 0val[u] 0刚好平衡这一整块自己就是一个完美块。你看原来要盯着两个数字看现在只看一个val的符号和是否为 0 就够了。这一步转化是整道题的第一块基石也是01价值这个标签最直接的体现。2.2 状态定义与转移val 与 dp 的双线并行正式定义状态。我用两个数组val[u]以 u 为根的子树把已经独立出去的完美块全部忽略之后u 所在的那一块还欠多少账也就是它的价值差dp[u]以 u 为根的子树内部已经能确定下来的完美块数量。转移的时候先递归处理所有儿子 v把dp[v]累加到dp[u]再把val[v]累加到val[u]。等所有儿子都合并完之后看自己的val[u]如果val[u] 0说明以 u 为根的这整块刚好平衡可以把它作为一块切出去于是dp[u] 1如果val[u] ! 0说明这一块自己平不了只能继续往上并给父节点dp[u]不变。最后看根节点如果val[root] ! 0意味着整棵树都平不了直接输出 -1否则输出dp[root]。整套状态转移就这两行简单得有点反直觉。2.3 贪心正确性的证明切掉平衡子树永远不亏这里必须停下来证明一下否则能切就切就是拍脑袋。关键点在于只有val为 0 的子树才会被切出去而它的价值贡献本来就是 0。假设某个子树 u 满足val[u] 0我们把它和父节点之间的边删掉。对父节点来说原本要累加val[u]现在不累加了但val[u]是 0加不加结果一样。也就是说切掉这棵子树完全不会影响上层任何节点的平衡状态上层的可行性既没变好也没变差。既然对上层零影响而切掉之后能实打实多出一块那切一定不比不切差贪心选择成立。反过来如果val[u] ! 0那这棵子树无论如何都没法自己凑成完美块它必须和上层合并才有可能补齐。所以不切是唯一的选择不存在纠结空间。两个方向合起来就证明了自底向上能切就切就是全局最优。这个论证是整个题解的灵魂面试或者赛后复盘的时候能把这段话讲清楚比背代码有价值得多。3. 完整实现从读入到输出的每一行3.1 存图与输入格式的几个细节先说输入。常见格式是第一行读 n第二行读 n 个整数表示每个节点的颜色0 或 1后面 n-1 行每行两个整数表示一条边。具体格式以题面为准我这里按最常见的一种写。n 一般到 1e5 甚至更大边数 n-1用邻接表存图最稳妥别用邻接矩阵那玩意儿 O(n²) 的空间直接就爆了。我习惯用vectorint g[MAXN]来存加边的时候正反各加一次因为是无根树。注意题目给的是无根树需要自己定一个根。定哪个点当根都行结果一样我一般直接拿 1 号点当根。这里有个坑如果节点编号从 0 开始那就拿 0 号当根别写死成 1否则会少处理一个点莫名其妙错答案。注意无根树转有根树时一定要用一个parent数组或者传参把父节点记住否则 DFS 会往回走直接死循环或者爆栈。3.2 迭代写法为什么我劝你别用递归按理说树形DP用递归最自然几行就写完了。但我踩过一次坑n 到 1e5、树退化成一条链的时候递归深度直接 1e5Windows 下默认栈空间不够程序当场崩评测机上能不能过全看运气。所以现在我一律用迭代版。迭代的思路很简单先手动做一遍 DFS 求出遍历顺序order然后逆序处理这个序列。因为 DFS 序里父节点一定排在子节点前面逆序处理就能保证每次轮到某个节点时它的所有儿子都已经算完了。这样既避免了递归爆栈代码也不长还顺手把父节点是谁这件事固化到了par数组里。3.3 参考代码下面这份是我实际跑过的版本C 写的逻辑就是前面讲的那套。val[u]是子树差值dp[u]是子树内已确定的完美块数量。#include bits/stdc.h using namespace std; static const int MAXN 100005; int color[MAXN], par[MAXN], val[MAXN], dp[MAXN]; vectorint g[MAXN]; int main() { int n; if (scanf(%d, n) ! 1) return 0; for (int i 1; i n; i) scanf(%d, color[i]); 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 求遍历序 vectorint order; order.reserve(n); vectorint st; st.push_back(1); par[1] 0; while (!st.empty()) { int u st.back(); st.pop_back(); order.push_back(u); for (int v : g[u]) { if (v par[u]) continue; par[v] u; st.push_back(v); } } // 逆序处理保证子节点先于父节点 for (int i (int)order.size() - 1; i 0; i--) { int u order[i]; val[u] (color[u] 0 ? 1 : -1); dp[u] 0; for (int v : g[u]) { if (v par[u]) continue; val[u] val[v]; dp[u] dp[v]; } if (val[u] 0) dp[u] 1; // 这一块刚好平衡切出去 } if (val[1] ! 0) printf(-1\n); else printf(%d\n, dp[1]); return 0; }代码里val[u]初始化为color[u] 0 ? 1 : -1这就是价值转化的落点。逆序处理时先把自己算进去再把所有儿子的val和dp累加进来最后判断val[u] 0决定要不要1。三件事加起来不超过十行。3.4 手推三组样例验证光看代码不到位我拿三组数据走一遍。第一组n 4边是 1-2、2-3、2-4颜色依次是 0、0、1、1。叶节点 3、4 的val都是 -1dp都是 0。节点 2 的val 1 -1 -1 -1不为 0所以dp[2] 0。节点 1 的val 1 (-1) 0dp[1] dp[2] 1 1。输出 1也就是整棵树本身就是一块完美块对得上。第二组n 4边是 1-2、2-3、1-4颜色依次是 0、0、1、1。节点 3 的val -1dp 0节点 2 的val 1 -1 0于是dp[2] 0 1 1节点 2 这棵子树切出去成了{2,3}黑白各一个。节点 4 的val -1dp 0。节点 1 的val 1 0 (-1) 0dp[1] dp[2] dp[4] 1 2。输出 2也就是{2,3}和{1,4}两块都平衡正确。第三组n 3 一条链 1-2-3颜色全是 0。节点 3 的val 1节点 2 的val 2节点 1 的val 3不为 0输出 -1。三个 0 凑不出平衡确实无解。三组跑下来逻辑没有漏。4. 踩坑实录与提速排查4.1 无解判断别放在错的位置最常见的一个错误是把-1的判断写在了 DFS 里面比如看到某个节点val ! 0就急着输出 -1。这是错的。一个子树val ! 0太正常了它只是没法自己成块还得往上并不代表整棵树不行。真正的无解只有一个条件根节点的val ! 0。因为所有没法自己成块的子块最后都会并到根这里根要是也平不了那就真的没救。所以这个判断只能放在最后而且必须看根。4.2 递归爆栈的两种救法前面提过递归爆栈。如果你就是想用递归有两个办法。一是手动开大栈空间在编译参数里加-Wl,--stack134217728之类的设置Linux 下用ulimit -s调整二是老老实实改迭代就像我上面那样。我个人推荐迭代因为赛场上你没法保证评测机的栈设置改迭代虽然多写几行但心里踏实。还有个小细节用vector当栈的时候注意reserve一下别让它反复扩容n 大的时候这点开销也不能忽略。注意迭代 DFS 里判断if (v par[u]) continue;只能挡住往回走的那条边。如果你的建图里有重边同一对点加了两次这个条件挡不住需要用visited数组再确认一次。4.3 根节点到底算不算一块这个问题很多人卡。答案是算。如果根节点的val 0那根所在的整块也是一个完美块dp[root]在计算时已经把它1进去了别再手动补。反过来如果根val ! 0那它连自己都不平衡整棵树无解dp里那一块也不会被加上。所以判断顺序一定要是先算dp[root]再看val[root]是否为 0两者不冲突但别写反。4.4 常见错误速查表现象可能原因排查方向输出恒为 -1无解判断写在了子树里只判断根节点val答案比预期少 1根节点那块没算进去检查val[root]0时是否1程序崩溃或超时递归过深或图存得太大改迭代、换邻接表小数据对大数据错节点编号从 0 开始根写死成 1按实际编号选根死循环没记父节点DFS 往回走加par数组或visited这张表是我自己调这题时踩过的真实坑基本覆盖了新手会遇到的九成问题。定位问题的顺序建议是先看根判断对不对再看累加方向有没有搞反最后才怀疑建图。5. 举一反三同一套骨架的四个变体5.1 最少切边数的版本把问题从最多块数换成最少切边数答案就是dp[root] - 1。因为在树上切 k 块必定删 k-1 条边块数定了边数就定了两个问题是同一道的正反面。想清楚这点遇到换皮题就不用重新推。5.2 方案计数版本如果题目改成有多少种删边方案能让每块都完美思路就变成计数。注意到每个val 0的非根子树都有切和不切两种选择而且互不影响于是答案就是 2 的幂指数等于满足val[u] 0且 u 不是根的节点个数。我第一次看到这个结论时还挺意外推一遍贪心正确性就明白了——正因为平衡子树切与不切对上层零影响两种选择才都合法。5.3 带边权的最小代价版本再进阶一点如果删每条边有代价要求总代价最小且每块完美那就不能无脑切了。这时val 0的子树变成可选切开你要比较切开的收益和代价。状态得改成dp[u][0/1]表示u 所在块是否已独立转移时对每个儿子做一次 01 抉择。这才是真·树形DP也最贴近01最大/小价值这个标签的严格含义。5.4 每块大小必须为偶数的版本有的变体会加一条每块节点数必须为偶数。由于完美块黑白相等它天然就是偶数大小所以这条约束在本题里是冗余的。但如果换成每块里 0 的个数至少为 2这类额外限制状态就不能只用差值了得同时记录 0 的个数状态会膨胀需要另想办法。这也提醒我们只要题目多加一条跟数量有关的限制原本简单的差值状态就可能不够用。最后分享一个小体会。这道题我前后写坏了三次原因都不在算法上而是栽在细节一次是把无解判断提前了一次是根节点那块忘了算还有一次是递归爆栈。后来我养成了一个习惯——凡是树上自底向上的题先把状态含义用一句人话写下来比如这题就是我这一坨还欠多少账、已经凑出了几块。这句话写清楚了代码基本不会偏。这比上来就敲键盘有效得多。