题目大意
在一棵带权树上选择 \(k\) 个节点染成黑色，其余节点染成白色，使得所有黑点对距离之和加上所有白点对距离之和最大。
问题转化
暴力枚举的时间复杂度是 \(O(2^n)\)，对于 \(n \leq 2000\) 不可接受。那么，这道题该如何入手呢？
关键：考虑每条边对总收益的贡献。
对于树中的一条边 \((u,v)\)，假设边权为 \(w\)：
- 设 \(u\) 一侧有 \(x\) 个黑点，\(sz[v] - x\) 个白点。
- 则 \(v\) 一侧有 \(k-x\) 个黑点，\((n-sz[v])-(k-x)\) 个白点。
这条边被黑点对经过的次数为：\(x \times (k-x)\)
这条边被白点对经过的次数为：\((sz[v]-x) \times (n-k-(sz[v]-x))\)
因此，这条边的总贡献为：
\[w \times \left[ x \times (k - x) + (sz[v] - x) \times (n - k - sz[v] + x) \right]
\]
Solution
标签：树形DP/树上背包
- 状态定义
\(dp[u][j]\) 表示以 \(u\) 为根的子树中，选择 \(j\) 个黑点时，子树内能获得的最大收益。 - 状态转移
对于节点 \(u\) 的每个子节点 \(v\)，考虑在子树 \(v\) 中选择 \(t\) 个黑点（\(0 \leq t \leq \min(j, sz[v])\)）：
- 子树 \(v\) 内部已经贡献了 \(dp[v][t]\)。
- 边 \((u,v)\) 的贡献为：
\[w \times [t \times (k-t) + (sz[v]-t) \times (n-k-sz[v]+t)]
\]
- \(u\) 的其他子树选择 \(j-t\) 个黑点，贡献为 \(dp[u][j-t]\)。
因此：
\[dp[u][j] = \max_{0 \leq t \leq \min(j, sz[v])} \{dp[u][j-t] + dp[v][t] + w \times [t \times (k-t) + (sz[v]-t) \times (n-k-sz[v]+t)]\}
\]
时间复杂度
总时间复杂度：\(O(n^2)\)
对于 \(n \leq 2000\)，可以接受。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define N 2010
typedef long long ll;ll n, m; // n: 节点数, m: 要选择的黑点数(k)
ll sz[N]; // sz[i]: 以i为根的子树大小
ll head[N], to[N << 1], nxt[N << 1], nw[N << 1], cnt;
ll dp[N][N]; // dp[i][j]: 以i为根的子树中选择j个黑点的最大收益void dfs(ll u, ll f) {sz[u] = 1; // 自身大小dp[u][0] = dp[u][1] = 0; // 初始化：选0个或1个黑点收益为0// 遍历所有子节点for (ll i = head[u]; i; i = nxt[i]) {ll v = to[i];if (v == f) continue; dfs(v, u); // 递归处理子节点sz[u] += sz[v]; // 更新子树大小// 合并子树v到u（类似01背包，倒序枚举）for (ll j = min(m, sz[u]); j >= 0; j--) {// 先考虑子树v全白的情况（t=0）if (dp[u][j] != -1) {// 边(u,v)的贡献：子树v中所有点都是白色dp[u][j] += dp[v][0] + sz[v] * (n - m - sz[v]) * nw[i];}// 考虑子树v中选择t个黑点（t>0）for (ll t = min(j, sz[v]); t > 0; t--) {if (dp[u][j - t] == -1) continue; // 状态不可达// 计算边(u,v)的贡献ll edge_contrib = nw[i] * (t * (m - t) + (sz[v] - t) * (n - m - sz[v] + t));// 更新dp[u][j]dp[u][j] = max(dp[u][j], dp[u][j - t] + dp[v][t] + edge_contrib);}}}
}int main() {cin >> n >> m;for (ll i = 1; i < n; i++) {ll u, v, w;cin >> u >> v >> w;to[++cnt] = v;nxt[cnt] = head[u];head[u] = cnt;nw[cnt] = w;to[++cnt] = u;nxt[cnt] = head[v];head[v] = cnt;nw[cnt] = w;}// 初始化dp数组为-1（表示不可达状态）memset(dp, -1, sizeof(dp));dfs(1, 0);// 输出以1为根的树中选择m个黑点的最大收益cout << dp[1][m];return 0;
}