企业官网建设流程全解析

1. 从一道经典题看树上背包的设计哲学

第一次看到“树上染色”这个标题，很多人会以为是一道简单的涂色问题，真正读进去才发现，它把树形结构、动态规划和组合计数揉在了一起，是一道非常典型的思维题。题目大意是：给定一棵包含 n 个节点的树，需要选出恰好 k 个节点染成黑色，其余染成白色，使得所有同色点对之间的距离之和最大，要求输出这个最大值。n 的规模通常在两千级别，k 也在 n 以内。

这道题之所以经典，是因为它表面上在求“点对距离和”，但直接枚举点对显然不现实。真正巧妙的转化在于：把点对距离的贡献拆解到每一条边上。一条边被多少对同色点“跨过”，它就对答案贡献多少次边权。于是问题从“选点”变成了“统计每条边两侧的黑白点数量”，这就是整道题的思维核心。

我把它归类为“思维+树上背包”，是因为它需要两步走：第一步是思维转化，把全局点对距离拆成边的贡献；第二步是用树上背包在 O(n²) 的复杂度内完成状态合并。这两步缺一不可，很多人卡在第一步想不通，也有人想通了转化却写不对背包的合并顺序。下面我会把这两层都拆开讲透，包括状态定义、转移方程、边界处理，以及我自己踩过的几个坑。

适合阅读这篇内容的人：已经掌握树形 DP 基础、会写简单的子树合并背包，但在处理“边贡献”这类转化时容易懵的读者；也适合想复习树上背包合并技巧、避免常见实现错误的朋友。哪怕你之前没做过这道题，跟着思路走一遍，也能理解这类“贡献拆解+树上背包”题目的通用套路。

2. 核心思路拆解：为什么要把点对距离拆到边上

2.1 直接枚举点对的复杂度灾难

先说说最朴素的想法。如果直接枚举所有黑点对和所有白点对，计算它们之间的距离再求和，复杂度是多少？选 k 个黑点的方案数是 C(n,k)，即便固定了一种染色方案，计算所有同色点对距离也需要对每对点求 LCA 或做一次遍历，单次就是 O(n²) 级别。整体复杂度直接爆炸，n 到两千根本跑不动。

所以必须换思路。这里的关键洞察是：树上任意两点之间的距离，等于它们路径上所有边权之和。既然每条边会被某些点对“经过”，那我们完全可以反过来，不去管具体是哪对点，而是统计每条边被多少对同色点经过，乘以边权，累加起来就是答案。这个转化把“点对”这个二维的对象，降维成了“边”这个一维的对象，复杂度一下子就可控了。

2.2 一条边的贡献到底怎么算

假设我们切掉某条边，树会被分成两部分：一侧是子树，大小记为 s；另一侧是剩余部分，大小记为 n−s。设子树内有 x 个黑点，那么子树内的白点就是 s−x 个；相应地，另一侧的黑点是 k−x 个，白点是 (n−s)−(k−x) 个。

这条边对答案的贡献来自两部分：同色点对跨越这条边。黑色点对跨越的数量是 x × (k−x)，白色点对跨越的数量是 (s−x) × ((n−s)−(k−x))。两者相加，再乘以这条边的边权，就是这条边的总贡献。

注意：这里的“跨越”指的是点对的两个端点分别位于边的两侧。只有这种情况，路径才会经过这条边。

这个公式是整个解法的基石。你会发现，一条边的贡献只和“子树大小 s”以及“子树内黑点数 x”有关，跟树的具体形状、点的具体位置都无关。这就为树上背包创造了条件：我们只需要在每棵子树里枚举它包含多少个黑点，就能算出这条边（子树根到父节点的那条边）的贡献。

2.3 为什么选择树上背包而不是其他方法

有了边的贡献公式，接下来的任务就是：在树上选出 k 个黑点，使得所有边的贡献之和最大。每条边的贡献依赖于它下方子树的黑点数，而子树之间是相互独立的（除了共享总黑点数 k 这个约束）。这种“子树内选若干点、子树间合并、总量受限”的结构，正是树上背包的标准形态。

对比其他方案：贪心显然不行，因为一条边选多少黑点会影响其他边；网络流建模也过于复杂，而且 n=2000 的规模用流算法不划算。树上背包的复杂度是 O(n²)，对于 n=2000 来说大约是四百万次操作，完全在可接受范围内。所以树上背包是这道题最自然、最高效的选择。

2.4 状态定义的确定

状态定义直接决定了转移方程的形式。我们设dp[u][j]表示：在以 u 为根的子树中，选出 j 个黑点，能够获得的最大贡献（这里只计算子树内部已经确定的边的贡献，u 到父节点那条边的贡献留到父节点合并时再算）。

为什么要把 u 到父节点的边留到后面算？因为这条边的贡献依赖于“子树大小”和“子树黑点数”，而子树大小在合并过程中是动态增长的，只有在 u 的整棵子树确定后，这条边的贡献才能算准。所以我们在处理 u 的时候，先算它所有子边的贡献，最后在父节点处再补上 u 这条边的贡献。

这种“延迟计算”是树上背包处理边贡献类问题的常见技巧，理解这一点能避免很多状态混乱。

3. 树上背包的转移细节与实现要点

3.1 子树合并的基本框架

树上背包的核心操作是：把一个个子节点的背包合并到当前节点上。假设当前节点 u 已经合并了若干子树，当前背包大小为sz[u]（已合并部分的节点数），现在要合并子节点 v，v 的子树大小为sz[v]。

合并时，我们枚举 u 当前已选的黑点数 j，以及 v 子树中选的黑点数 t，那么合并后的黑点数是 j+t。转移方程大致是：

dp[u][j+t] = max(dp[u][j+t], dp[u][j] + dp[v][t] + 边(u,v)的贡献)

这里的“边(u,v)的贡献”就是前面推导的公式，其中 s = sz[v]，x = t。注意这条边是 u 到 v 的边，它下方是 v 的子树，所以用 v 的子树大小和 v 子树的黑点数来计算。

3.2 合并顺序与倒序枚举的必要性

这里有一个非常容易出错的点：合并背包时，枚举 j 必须倒序。原因和 01 背包一模一样——如果我们正序枚举 j，那么dp[u][j]可能在本次合并中已经被更新过，再用来更新更大的 j 就会导致同一个子节点被重复使用。

具体来说，正确的写法是：

for (int j = min(sz[u], k); j >= 0; j--) { for (int t = 0; t <= min(sz[v], k - j); t++) { long long contrib = 1LL * t * (k - t) + 1LL * (sz[v] - t) * ((n - sz[v]) - (k - t)); dp[u][j + t] = max(dp[u][j + t], dp[u][j] + dp[v][t] + contrib * w); } }

外层 j 倒序，内层 t 正序或倒序都可以（因为 t 来自子节点 v 的背包，不会和 u 的背包冲突）。但 j 一定要倒序，这是保证每个子节点只被合并一次的关键。

实操心得：我见过不少人把 j 写成正序，小数据能过，大数据就错，而且很难 debug。记住一句话——只要是从“旧状态”转移到“新状态”且新旧共用同一个数组，就要考虑倒序。

3.3 复杂度分析与剪枝技巧

朴素写法下，合并 u 和 v 的复杂度是 O(sz[u] × sz[v])。所有子树合并的总复杂度是 O(n²)，这是树上背包的经典结论。证明思路是：任意两个节点只会在它们的 LCA 处被“配对”一次，所以总配对数是 O(n²)。

不过实际写的时候，如果不加剪枝，常数会比较大。两个常用优化：

• 枚举 j 的上界用min(sz[u], k)，而不是直接到 k，避免大量无效枚举。
• 枚举 t 的上界用min(sz[v], k - j)，保证 j+t 不超过 k。

这两个剪枝能把实际运行时间压下来不少。对于 n=2000 的数据，优化后基本能稳定在几十毫秒级别。

3.4 边界条件与初始化

初始化方面，dp[u][0] = 0，dp[u][1] = 0（如果允许 u 自己染黑），其余为负无穷。这里要注意：如果题目要求恰好选 k 个黑点，那么最终答案是dp[root][k]；如果允许少于 k 个，则要取 max。本题是恰好 k 个，所以直接取dp[1][k]。

另外，叶子节点的处理要小心。叶子没有子节点，它的背包就是dp[leaf][0]=0, dp[leaf][1]=0，sz[leaf]=1。在父节点合并时，叶子到父节点那条边的贡献会按照 s=1 来计算，这是正确的。

注意：负无穷不要用 INT_MIN，因为转移时要加贡献值，容易溢出。建议用 -1e18 这种量级，并且用 long long 存储。

4. 完整实现流程与关键代码解析

4.1 建树与预处理

首先读入 n 和 k，然后读入 n−1 条边，每条边包含两个端点和边权。用邻接表存图，注意是无向边，要存双向。然后从根节点（通常选 1）开始做一次 DFS，预处理出每个节点的子树大小sz[u]。

void dfs_size(int u, int fa) { sz[u] = 1; for (auto &e : g[u]) { int v = e.to; if (v == fa) continue; dfs_size(v, u); sz[u] += sz[v]; } }

这一步是基础，子树大小在后续计算边贡献时反复用到，必须先算好。

4.2 树上背包的递归实现

接下来是核心的 DP 过程。我习惯用递归写法，逻辑清晰，不容易出错：

void dfs_dp(int u, int fa) { dp[u][0] = 0; if (k >= 1) dp[u][1] = 0; int cur_sz = 1; for (auto &e : g[u]) { int v = e.to; long long w = e.w; if (v == fa) continue; dfs_dp(v, u); for (int j = min(cur_sz, k); j >= 0; j--) { if (dp[u][j] < 0) continue; for (int t = 0; t <= min(sz[v], k - j); t++) { if (dp[v][t] < 0) continue; long long black = 1LL * t * (k - t); long long white = 1LL * (sz[v] - t) * ((n - sz[v]) - (k - t)); long long contrib = (black + white) * w; dp[u][j + t] = max(dp[u][j + t], dp[u][j] + dp[v][t] + contrib); } } cur_sz += sz[v]; } }

这里用cur_sz记录当前已合并的节点数，代替sz[u]作为枚举上界，因为sz[u]是整棵子树的大小，而合并过程中可用的大小是逐步增长的。用cur_sz能进一步减少无效枚举。

4.3 边贡献计算的参数代入

再强调一遍边贡献的计算。对于边 (u,v)，v 是子节点，s = sz[v]，x = t（v 子树中选的黑点数），总黑点数 k，总节点数 n。代入公式：

• 黑色跨越：t × (k − t)
• 白色跨越：(sz[v] − t) × ((n − sz[v]) − (k − t))
• 贡献 = (黑色跨越 + 白色跨越) × 边权

这个计算在每次转移时都要做一次，所以尽量把能提前算的算好。比如n - sz[v]和k - t可以提前算，减少重复计算。

4.4 最终答案的提取

DP 结束后，答案就是dp[1][k]（假设 1 是根）。如果根节点也可以染黑，那么dp[1][k]已经包含了根节点染黑的情况；如果根节点必须染白，则要取dp[1][k]中根节点为白的状态，但本题没有这个限制，所以直接输出即可。

提示：如果题目要求输出方案数而不是最大值，转移方程要改成加法，并且要注意取模。本题是求最大值，所以用 max。

5. 常见问题与排查技巧实录

5.1 答案偏小或偏大：检查贡献公式

最常见的错误就是贡献公式写错。比如把黑色跨越写成t * (k - t)没问题，但白色跨越容易写成(sz[v] - t) * (n - sz[v] - (k - t))，注意括号位置。还有一种错误是忘记乘边权，或者边权用了 int 导致溢出。

排查方法：拿一个 n=2 的小例子手动算。两个节点一条边，k=1。选一个黑点一个白点，同色点对为 0，答案应该是 0。如果程序输出非 0，说明公式有问题。

5.2 背包合并顺序错误导致重复使用

前面说过 j 要倒序。如果正序，会出现同一个子节点被合并多次的情况，答案会偏大。排查方法：构造一条链，n=3，k=1，手动算答案，对比程序输出。如果偏大，大概率是顺序问题。

5.3 负无穷初始化不当导致溢出

如果用INT_MIN作为负无穷，转移时加贡献会溢出成很大的正数，导致错误答案。建议用-1e18并且用 long long。另外，在转移前判断dp[u][j] < 0可以跳过无效状态，既提速又避免溢出。

5.4 子树大小与当前合并大小的混淆

sz[v]是 v 的整棵子树大小，这个在计算边贡献时必须用。而cur_sz是 u 当前已合并的节点数，用于枚举上界。两者不能混用。我见过有人把cur_sz当成sz[v]去算贡献，结果全错。

5.5 常见问题速查表

实操心得：这道题我建议先用暴力枚举所有 C(n,k) 种染色方案，对拍小数据（n≤10），确认 DP 正确后再提交。对拍是发现逻辑错误最快的方法，比盯着代码看有效得多。

6. 从这道题延伸出的通用套路

6.1 贡献拆解法的适用场景

“把点对距离拆到边上”这个技巧，不只适用于染色问题。凡是涉及“树上点对距离之和”的题目，都可以考虑这种转化。比如求所有点对距离和、求同色点对距离和、求满足某种条件的点对距离和，思路都是一样的：统计每条边被多少对满足条件的点经过。

判断能不能用这个套路，关键看“点对是否满足条件”能否转化为“边两侧的某种计数”。如果能，就可以把 O(n²) 的点对枚举降成 O(n) 的边统计。

6.2 树上背包的合并模板

树上背包的合并框架非常固定，可以总结成模板：

void dfs(int u, int fa) { // 初始化 dp[u] int cur = 1; for (int v : children[u]) { dfs(v, u); for (int j = min(cur, K); j >= 0; j--) { for (int t = 0; t <= min(sz[v], K - j); t++) { // 转移 } } cur += sz[v]; } }

只要把“转移”部分替换成具体题目的逻辑，就能套用到很多题上。比如树上选点、树上分组、树上依赖背包等。

6.3 复杂度优化的通用思路

树上背包的 O(n²) 已经是理论下界（因为要枚举所有点对组合），但常数可以优化。除了前面说的剪枝，还可以用“按子树大小排序”来减少合并代价——先合并小的子树，能让 cur 增长得慢一些，减少无效枚举。这个技巧在 n 较大时效果明显。

另外，如果 k 远小于 n，可以把枚举上界限制在 k 以内，复杂度降到 O(nk)。本题 k 和 n 同阶，所以还是 O(n²)。

6.4 类似题目的推荐练习路径

如果你想巩固这个套路，可以按这个顺序练：

1. 先做基础的树上背包（如选课问题），熟悉合并框架。
2. 再做带边贡献的题目（如本题），理解贡献拆解。
3. 最后做带复杂约束的树上背包（如分组背包、依赖背包），提升综合能力。

每道题做完后，试着总结“状态定义、转移方程、边界处理”三要素，形成自己的模板库。这样下次遇到新题，能快速识别出它属于哪一类，该用什么套路。

我个人在实际操作中的体会是，树上背包这类题目，想清楚“每条边的贡献怎么算”比写代码更重要。代码写错了可以调，思路错了就全盘皆输。所以拿到题先别急着敲键盘，花十分钟把贡献公式推导一遍，把状态定义写清楚，再动手实现，效率反而更高。另外，对拍真的能救命，尤其是这种转移容易写错的题，花五分钟写个暴力，能省下半小时的 debug 时间。