企业官网建设流程全解析

1. 从一道题看树上背包的本质

1.1 这道题到底在问什么

先把题意用大白话翻译一遍。给你一棵有 n 个节点的树，再给你一个数字 k，要求你从这 n 个节点里选出恰好 k 个节点染成黑色，剩下的 n-k 个节点就是白色。染完之后，每一对同色节点（黑-黑、白-白）之间都会产生贡献，贡献值等于它们在树上的距离。你要做的就是选一种染色方案，让所有同色点对的距离之和最大。

我第一次读完题的反应是：这玩意儿怎么下手？因为距离这个东西是全局的，你染一个点，会影响到它和所有同色点的距离，看起来牵一发动全身。但真正做过之后你会发现，这题的精髓在于换一个统计视角——不要盯着"点对"去算距离，而是盯着"边"去算贡献。

这个视角转换是整道题的分水岭。想通了这一点，后面的树上背包就是水到渠成；想不通，你会在点对的泥潭里越陷越深。

1.2 为什么是"思维+树上背包"

标题里给的定位非常准确：思维 + 树上背包。这两个词缺一不可。

"思维"指的是上面说的那条边贡献的转化思路。这是这道题真正的门槛，也是它被归为思维题的原因。很多人背包写得滚瓜烂熟，但卡在这一步就是出不来。

"树上背包"指的是在树形结构上做分组背包式的 DP。每个子树是一个"组"，我们在子树内部决定染多少个黑点，然后把子树的信息合并到父节点。这是树形 DP 里非常经典的一类套路，但这道题的合并代价不是简单的加法，而是带着"边贡献"的系数，所以细节上比模板题要绕。

适合谁来读这篇？如果你已经会写基础的树形 DP（比如求子树大小、求树上最长路径），但一遇到"树上背包"就发怵，或者你做过这道题但当时是抄的题解、没真正理解为什么这么设计状态，那这篇就是写给你的。我会把状态定义、转移方程、边界处理、复杂度分析全部拆开讲，并且告诉你哪些地方是坑。

2. 核心思维：把点对距离拆到边上

2.1 一条边到底贡献了多少次

这是整道题最关键的洞察，我把它单独拎出来讲透。

树上两点 u、v 之间的距离，等于它们路径上所有边的长度之和。如果每条边的长度都是 1，那距离就等于路径上的边数。现在我们要统计所有同色点对的距离总和，等价于：对每一条边，统计它被多少个同色点对"经过"，然后把这些次数加起来。

为什么可以这样拆？因为距离本身就是边数的累加，而"求和"这个操作是可以交换顺序的。原本是"先枚举点对、再累加路径上的边"，现在换成"先枚举边、再看有多少点对经过它"，结果完全一样。这就是所谓的贡献法，或者叫拆边统计。

那么对于一条边 e，它把树分成了两个部分：一边是子树 S（假设是节点 v 及其后代），另一边是剩下的部分。设子树 S 的大小为 sz，那么：

• 子树内有 sz 个节点，子树外有 n - sz 个节点。
• 一条边被一对同色点对经过，当且仅当这两个点分别位于边的两侧。

所以对于边 e，假设子树 S 里有 x 个黑点，那么子树外就有 k - x 个黑点。这条边贡献的黑-黑点对数量就是：

x * (k - x)

同理，子树 S 里有 sz - x 个白点，子树外有 (n - k) - (sz - x) 个白点。这条边贡献的白-白点对数量是：

(sz - x) * ((n - k) - (sz - x))

两者相加，就是这条边对答案的总贡献：

val(e) = x * (k - x) + (sz - x) * ((n - k) - (sz - x))

看到这个式子，你应该能立刻意识到：一条边的贡献只取决于它下方子树里染了多少个黑点。这就是为什么我们可以用 DP 来做——每条边的贡献是局部的、可计算的，不依赖全局的具体染色分布。

2.2 为什么这个转化如此重要

如果你不走这条路，硬去枚举点对，那复杂度至少是 O(n²) 起步，n 到 2000 的时候勉强能过，但状态设计和转移会非常恶心，因为你没法把"某个点和其他所有同色点的距离"这种全局信息塞进子树 DP 里。

而拆到边上之后，每条边的贡献变成了一个只和"子树黑点数"有关的一元函数。这就把全局问题彻底局部化了。子树 DP 最擅长的就是处理"子树内部选了多少个"这类信息，两者一拍即合。

我个人的经验是：凡是树上统计"点对距离之和"的题，第一反应就应该是拆边。这个套路在树上问题里出现频率极高，比如求所有点对距离和、求带权点对距离和等等。这道题只是给它加了一个"同色"的约束，本质没变。

提示：拆边统计的前提是"距离 = 边权之和"，如果边权不是 1，把式子里的 1 换成边权即可，思路完全一样。这道题边权为 1，所以直接数点对数就行。

3. 树上背包的状态设计与转移

3.1 状态定义：dp[u][j] 的含义

有了边的贡献公式，状态就呼之欲出了。我们定义：

dp[u][j] = 在以 u 为根的子树中，选出 j 个黑点，子树内部所有边的贡献之和的最大值

注意这里的关键词：子树内部所有边。也就是说，dp[u][j] 只统计 u 的子树里那些边的贡献，不包括 u 连向父节点的那条边。为什么？因为那条边的贡献取决于整棵子树染了多少黑点，而子树染多少黑点这件事，在父节点合并的时候才能确定。所以父边贡献留到父节点去算，这是树形 DP 的常规操作。

那么最终答案是什么？根节点没有父边，所以根节点的 dp[root][k] 就是所有边的贡献之和，也就是答案。

这里有个容易绕晕的点：dp[u][j] 里的 j 是"子树里黑点的总数"，而不是"子树里某个局部的黑点数"。这个 j 会一路向上传递，父节点合并子节点时，把子节点的 j 累加起来。所以整个 DP 的过程，本质上是在做"子树黑点数的分配"。

3.2 转移方程怎么推

假设我们现在在处理节点 u，它有一个子节点 v。我们已经算好了 dp[v][*]，现在要把 v 这棵子树合并进 u。

设合并前 u 已经处理过的部分（包括 u 自己和其他已合并的子树）有 j1 个黑点，v 子树里有 j2 个黑点。合并后 u 的部分就有 j1 + j2 个黑点。

合并的时候，我们需要加上边 (u, v) 的贡献。这条边下方是 v 的子树，子树大小是 sz[v]，子树里有 j2 个黑点。套用前面的公式：

edge_contrib = j2 * (k - j2) + (sz[v] - j2) * ((n - k) - (sz[v] - j2))

所以转移就是：

dp[u][j1 + j2] = max(dp[u][j1 + j2], dp[u][j1] + dp[v][j2] + edge_contrib)

这就是树上背包的标准形式。外层枚举 j1，内层枚举 j2，做一次类似背包的合并。

3.3 初始化与边界

初始化很关键，写错了整个 DP 就崩了。

对于每个节点 u，初始时它自己就是一个"部分"，此时：

dp[u][0] = 0 // 不选 u 为黑点 dp[u][1] = 0 // 选 u 为黑点

其他 dp[u][j] 初始化为负无穷（表示不可达）。为什么是 0 而不是别的？因为此时还没有任何边被统计，子树内部边贡献为 0。

然后对于每个子节点 v，先递归算出 dp[v][*]，再做合并。合并的时候要注意：j1 的上界是当前已合并部分的节点数，j2 的上界是 sz[v]。这个上界控制是保证复杂度的关键，后面会细说。

还有一个边界：j 不能超过 k，因为总共只染 k 个黑点。所以所有 dp 的第二维都限制在 [0, k] 范围内。

注意：dp 数组要开成 dp[n][k+1]，并且每次合并前要把新的一维清成负无穷。我见过太多人在这里忘记清空，导致上一轮的值残留，答案偏大。

4. 复杂度分析与优化细节

4.1 朴素写法为什么是 O(n²)

很多人一看树上背包，觉得每对父子都要枚举 j1 和 j2，复杂度是不是 O(n³)？其实不是，标准分析下来是 O(n²)。

关键在于枚举上界的控制。合并子节点 v 时，j1 的上界是"当前已合并部分的节点数"，j2 的上界是 sz[v]。如果我们用两个变量 cur 和 sz[v] 来限制循环范围，那么总的合并代价等于"所有点对的 LCA 关系数"，也就是 O(n²)。

具体来说，每一对节点 (a, b) 会在它们的 LCA 处被枚举一次，总共 n² 对，所以是 O(n²)。这个分析在树上背包里是经典结论，n = 2000 的时候 n² = 4×10⁶，完全跑得动。

但如果你偷懒，j1 和 j2 都从 0 枚举到 k，那复杂度就退化成 O(n·k²)，k 最大也是 n，所以是 O(n³)，n = 2000 直接爆炸。所以上界控制不是优化，是必须。

4.2 上界控制的具体写法

合并时的循环应该这样写：

// cur 是当前 u 已合并部分的节点数 // sz[v] 是子节点 v 的子树大小 for (int j1 = min(cur, k); j1 >= 0; j1--) { if (dp[u][j1] == -INF) continue; for (int j2 = min(sz[v], k - j1); j2 >= 0; j2--) { if (dp[v][j2] == -INF) continue; int contrib = j2 * (k - j2) + (sz[v] - j2) * ((n - k) - (sz[v] - j2)); dp[u][j1 + j2] = max(dp[u][j1 + j2], dp[u][j1] + dp[v][j2] + contrib); } } cur += sz[v];

几个细节：

• j1 从大到小枚举，是为了避免同一棵子树被重复使用（类似 01 背包的倒序）。不过因为我们是先算 dp[v] 再合并，且 dp[u] 和 dp[v] 是分开的数组，其实正序也不会出错。但养成倒序的习惯没坏处。
• j2 的上界是 min(sz[v], k - j1)，因为合并后总数不能超过 k。
• 遇到负无穷直接 continue，能省不少时间。
• 合并完记得更新 cur。

4.3 一个容易忽略的坑：k 和 n-k 的对称性

这道题有一个很妙的性质：把 k 换成 n-k，答案不变。因为黑点和白点是对称的，你把所有颜色翻转，同色点对还是那些点对，距离和自然不变。

这个性质有什么用？当 k > n/2 的时候，我们可以令 k = n - k，这样背包的第二维就变小了，复杂度从 O(n·k) 降到 O(n·min(k, n-k))。虽然对 n = 2000 来说影响不大，但这是个好习惯，而且能体现你对问题结构的理解。

我在实际写的时候，会在读入后加一句：

if (k > n - k) k = n - k;

这样后面的 DP 维度更小，跑得更快。注意这不会改变答案，因为对称性保证了结果一致。

5. 完整实现与关键代码解析

5.1 建树与递归框架

树是给定的，n 个节点 n-1 条边。用邻接表存图，然后从节点 1 开始 DFS。

#include <bits/stdc++.h> using namespace std; const int MAXN = 2005; const long long INF = 1e18; int n, k; vector<int> g[MAXN]; int sz[MAXN]; long long dp[MAXN][MAXN]; // dp[u][j]: u 子树内选 j 个黑点，子树内部边的最大贡献 void dfs(int u, int fa) { sz[u] = 1; // 初始化：只考虑 u 自己 for (int j = 0; j <= k; j++) dp[u][j] = -INF; dp[u][0] = 0; if (k >= 1) dp[u][1] = 0; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); // 合并 v 子树 for (int j1 = min(sz[u], k); j1 >= 0; j1--) { if (dp[u][j1] == -INF) continue; for (int j2 = min(sz[v], k - j1); j2 >= 0; j2--) { if (dp[v][j2] == -INF) continue; long long contrib = 1LL * j2 * (k - j2) + 1LL * (sz[v] - j2) * ((n - k) - (sz[v] - j2)); dp[u][j1 + j2] = max(dp[u][j1 + j2], dp[u][j1] + dp[v][j2] + contrib); } } sz[u] += sz[v]; } }

主函数里读入、建边、调用 dfs(1, 0)，最后输出 dp[1][k]。

5.2 为什么用 long long

答案的量级估算一下：n = 2000，点对数最多约 n²/2 = 2×10⁶，每对距离最多 n = 2000，所以答案上界约 4×10⁹，超过了 int 的 2.1×10⁹。所以必须用 long long。

我见过有人用 int 然后 WA 在第 7 个点，就是因为溢出。这个坑很隐蔽，因为小数据看不出来，大数据直接爆。

5.3 递归深度问题

n = 2000 的时候，如果树退化成一条链，递归深度就是 2000。一般评测机的栈够用，但保险起见可以开大栈或者改迭代。不过 2000 这个量级通常没问题，我实测下来没遇到过爆栈。

如果你担心，可以在代码开头加：

// 某些环境下需要手动扩栈，或者用迭代写法

但大多数在线评测环境对 2000 层递归是能扛住的。

5.4 贡献公式的符号检查

再强调一遍贡献公式：

contrib = j2 * (k - j2) + (sz[v] - j2) * ((n - k) - (sz[v] - j2))

• 第一项：黑-黑点对。子树内 j2 个黑点，子树外 k - j2 个黑点，配对数 j2 × (k - j2)。
• 第二项：白-白点对。子树内白点 sz[v] - j2 个，子树外白点 (n - k) - (sz[v] - j2) 个。

注意第二项里子树外白点数是 (n - k) - (sz[v] - j2)，不是 (n - k) - j2。因为子树外白点 = 总白点 - 子树内白点 = (n - k) - (sz[v] - j2)。这个细节我第一次写的时候搞错了，把子树内白点数写成了 j2，结果答案完全不对。

提示：写公式的时候，把每个量的含义在纸上标清楚，别凭感觉写。这种地方错一个符号，整道题就废了。

6. 常见问题与排查实录

6.1 答案偏小或偏大

症状：样例过了，但提交后部分测试点 WA。

排查思路：

• 检查 dp 数组是否每次合并前清空。如果没清空，上一轮的值会残留，导致答案偏大。
• 检查贡献公式的符号。特别是白点那一项，子树外白点数容易写错。
• 检查是否用了 long long。溢出会导致答案偏小甚至变负。
• 检查 k 是否超过了 n。虽然题目一般保证 k ≤ n，但保险起见可以加个判断。

6.2 复杂度超时

症状：TLE。

排查思路：

• 检查 j1 和 j2 的上界是否用了 cur 和 sz[v] 控制。如果都枚举到 k，复杂度会退化到 O(n³)。
• 检查是否在循环里做了不必要的操作，比如每次都重新计算 contrib。contrib 只和 j2 有关，可以在内层循环外预处理。
• 如果 k > n/2，考虑用对称性把 k 换成 n-k。

6.3 递归爆栈

症状：RE 或者段错误。

排查思路：

• 树退化成链时递归深度为 n。n = 2000 一般没事，但如果 n 更大就要注意。
• 可以改写成迭代版的 DFS，或者手动扩栈。

6.4 常见问题速查表

6.5 独家避坑技巧

技巧一：先写暴力对拍。这道题的暴力很好写：枚举所有 C(n, k) 种染色方案，对每种方案算同色点对距离和，取最大。n 小的时候（比如 n ≤ 10）可以暴力，然后和你的 DP 对拍。我当年就是靠对拍发现了白点公式写错的问题。

技巧二：把贡献公式单独写成一个函数。这样方便调试，也方便你检查符号。比如：

long long edge_contrib(int sub_size, int sub_black) { int sub_white = sub_size - sub_black; int out_black = k - sub_black; int out_white = (n - k) - sub_white; return 1LL * sub_black * out_black + 1LL * sub_white * out_white; }

技巧三：注意 k = 0 或 k = n 的边界。这两种情况下所有点同色，答案是所有点对距离和。你的 DP 应该能正确处理，但值得单独测一下。

技巧四：对称性优化别忘了。虽然不影响正确性，但能体现你对问题的理解，而且实测能快不少。

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

7.1 树上背包的通用模板

这道题是树上背包的一个典型变种。标准的树上背包模板大概长这样：

void dfs(int u, int fa) { sz[u] = 1; dp[u][0] = 0; // 根据题意初始化 for (int v : g[u]) { if (v == fa) continue; dfs(v, u); for (int j1 = min(sz[u], K); j1 >= 0; j1--) { for (int j2 = min(sz[v], K - j1); j2 >= 0; j2--) { dp[u][j1 + j2] = max(dp[u][j1 + j2], dp[u][j1] + dp[v][j2] + cost); } } sz[u] += sz[v]; } }

区别只在于 cost 怎么算、初始化怎么写、答案是 dp[root][K] 还是 max(dp[root][*])。掌握这个模板，很多树上选点问题都能套。

7.2 贡献法的适用场景

贡献法的核心思想是：把全局的、难以直接统计的量，拆解成局部的、可以独立计算的量。在树上问题里，最常见的拆法就是拆到边上。

适用场景包括：

• 统计所有点对距离和
• 统计满足某种条件的点对数量
• 带权点对的贡献统计

判断能不能用贡献法，就看"每条边的贡献是否只依赖于子树内部的某个可 DP 的量"。如果是，那就能做。

7.3 复杂度分析的通用方法

树上背包的 O(n²) 分析，本质上是"每对节点在 LCA 处被枚举一次"。这个分析方法可以推广到很多树形 DP 问题。记住这个结论，以后遇到类似问题可以直接套。

如果第二维不是节点数而是别的量（比如颜色数、容量），那复杂度就是 O(n·K)，其中 K 是第二维的大小。这时候上界控制依然重要。

8. 我个人的一些实战体会

这道题我前前后后做了三遍。第一遍是照着题解抄的，抄完就忘；第二遍是自己推，卡在贡献公式上，白点那项写错了，调了一晚上；第三遍是给别人讲，讲着讲着突然就通透了。

我的体会是：树上背包的难点从来不在背包本身，而在状态定义和贡献计算。背包的合并逻辑是死的，套模板就行；但状态怎么定义、贡献怎么算，每道题都不一样，这才是真正考验思维的地方。

另外，这道题让我养成了一个习惯：遇到树上统计点对的问题，先想能不能拆边。这个思维惯性后来帮我秒杀了好几道类似的题。比如有一道题是求"所有黑点两两距离之和减去所有白点两两距离之和"，本质上还是拆边，只是贡献公式变了一下。

最后分享一个小技巧：如果你在推导贡献公式的时候卡住了，不妨画一棵只有 3 个节点的小树，手动枚举所有染色方案，把每条边的贡献算出来，然后对照你的公式验证。小数据验证通过之后，再推广到一般情况，心里就有底了。

这道题后续还可以这样扩展：如果边带权，把贡献公式里的点对数乘以边权即可；如果要求的是"同色点对距离的最小值最大"或者别的目标，那就不是背包能解决的了，可能需要换思路。但无论如何，拆边统计这个核心思维是不变的。