企业官网建设流程全解析

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和y，x+y=sz，要求|x-y|≤1。那么这个差值|x-y|的奇偶性，其实和sz的奇偶性是绑死的。因为x-y = x-(sz-x) = 2x-sz，2x是偶数，所以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时w=+1，定成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]。

我们定义三个值来描述子树v：dp0[v]表示v子树完美且差值为0的最小代价；dp1[v]表示差值为+1；dpm1[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]为偶数则delta=0，为奇数则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都反推出一个唯一确定的p：

p = (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个。这是一个无争议的贪心，不需要什么证明技巧。

不过这里藏着一个小陷阱，我要专门点一下：如果你为每个节点枚举所有可能的delta（0、+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²)，n=10⁵时是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最终的颜色。

对每个颜色col（0或1），基础代价c = cost_col[u]，w = (col==0 ? +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; vector<vector<int>> g; vector<long long> cost0, cost1; // 定成0/1的代价 vector<long long> dp0, dp1, dpm1; // 三种差值状态 vector<int> sz; void dfs(int u, int p) { sz[u] = 1; long long base = 0; vector<long 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(); vector<long 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时w=+1还是-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 特殊形态：单链、菊花、n=1

单链是最容易暴露奇偶性bug的形态。一条长度为n的链，每一层子树的奇偶性交替变化，你的状态切换逻辑如果有一点问题，单链上就会立刻出错。建议手动构造n=1、2、3、4的链，逐个手算验证。

菊花图（根连着一堆叶子）也值得测。此时根的子节点全是叶子，每个都是奇数子树，m就等于叶子数，转移里"恰好选p个取+1"的作用会被放大到极致，能有效检验你的贪心选法。

n=1的情况更别漏，此时根就是叶子，没有子节点，m=0，delta只能是w=±1，答案就是min(cost0[1], cost1[1])。我见过有人在这种边界上因为数组下标或者循环写的直接RE。

最后分享一个我自己踩过的坑：优化的时候我一度想省掉排序，直接用"所有负增量必选、正增量按需补"，结果发现当p小于负增量个数时也没问题，但当p大于负增量个数时逻辑就变得很绕，容易越写越乱。老老实实排序取前p个，几十行代码清清楚楚，何必跟自己较劲。这道完美树，绕了一大圈，最后落在"排序取最小的p个"这么一个朴素的结论上，反倒让我觉得——约束越强、状态越少，题目反而越优雅。