企业官网建设流程全解析

整整一届天梯赛打完，群里讨论最热的往往不是最后的压轴，而是那种"名字唬人、读完有思路、下笔全是坑"的题。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 记 +1，1 记 -1，那么子树的价值就是它内部所有节点的权重之和。

设val[u]表示以 u 为根的子树的价值和。这个值有个非常直观的含义：它等于"子树里 0 的个数减去 1 的个数"。所以：

• val[u] > 0：这块里 0 比 1 多，欠着 1；
• val[u] < 0：这块里 1 比 0 多，欠着 0；
• val[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²) 的空间直接就爆了。

我习惯用vector<int> g[MAXN]来存，加边的时候正反各加一次，因为是无根树。注意：题目给的是无根树，需要自己定一个根。定哪个点当根都行，结果一样，我一般直接拿 1 号点当根。这里有个坑：如果节点编号从 0 开始，那就拿 0 号当根，别写死成 1，否则会少处理一个点，莫名其妙错答案。

注意：无根树转有根树时，一定要用一个parent数组或者传参把父节点记住，否则 DFS 会往回走，直接死循环或者爆栈。

3.2 迭代写法：为什么我劝你别用递归

按理说树形DP用递归最自然，几行就写完了。但我踩过一次坑：n 到 1e5、树退化成一条链的时候，递归深度直接 1e5，Windows 下默认栈空间不够，程序当场崩，评测机上能不能过全看运气。所以现在我一律用迭代版。

迭代的思路很简单：先手动做一遍 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]; vector<int> 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 求遍历序 vector<int> order; order.reserve(n); vector<int> 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都是 -1，dp都是 0。节点 2 的val = +1 -1 -1 = -1，不为 0，所以dp[2] = 0。节点 1 的val = +1 + (-1) = 0，dp[1] = dp[2] + 1 = 1。输出 1，也就是整棵树本身就是一块完美块，对得上。

第二组：n = 4，边是 1-2、2-3、1-4，颜色依次是 0、0、1、1。节点 3 的val = -1，dp = 0；节点 2 的val = +1 -1 = 0，于是dp[2] = 0 + 1 = 1，节点 2 这棵子树切出去成了{2,3}，黑白各一个。节点 4 的val = -1，dp = 0。节点 1 的val = +1 + 0 + (-1) = 0，dp[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,--stack=134217728之类的设置（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 常见错误速查表

这张表是我自己调这题时踩过的真实坑，基本覆盖了新手会遇到的九成问题。定位问题的顺序建议是：先看根判断对不对，再看累加方向有没有搞反，最后才怀疑建图。

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 的个数，状态会膨胀，需要另想办法。这也提醒我们：只要题目多加一条跟"数量"有关的限制，原本简单的差值状态就可能不够用。

最后分享一个小体会。这道题我前后写坏了三次，原因都不在算法上，而是栽在细节：一次是把无解判断提前了，一次是根节点那块忘了算，还有一次是递归爆栈。后来我养成了一个习惯——凡是树上自底向上的题，先把"状态含义用一句人话写下来"，比如这题就是"我这一坨还欠多少账、已经凑出了几块"。这句话写清楚了，代码基本不会偏。这比上来就敲键盘有效得多。