题目蓝链 https://www.luogu.org/problemnew/show/P3177
Description
给定一棵有 \(n\) 个节点的树, 初始全为白色. 你要在里面找到 \(k\) 个点, 并把它们染成黑色. 要使得染完色后, 黑点两两之间的距离加上白点两两之间的距离的和最大
Solution
我们可以设 \(dp[i][j]\) 表示以 \(i\) 为根的子树中选择 \(j\) 个节点对全局答案的最大贡献
然后对于每一个非叶子节点, 枚举儿子子树进行转移
\[ dp[u][j + k] \leftarrow dp[u][j] + dp[v][k] + val \]
其中 \(val\) 为以 \(v\) 为根的子树内的点通过对全局答案的贡献
至于时间复杂度, 我们可以发现任意一对点只会在它们 LCA 处被计算一次, 所以复杂度为 \(\mathcal{O}(n^2)\)
- Code
- #include <bits/stdc++.h>
- using namespace std;
- #define fst first
- #define snd second
- #define mp make_pair
- #define squ(x) ((LL)(x) * (x))
- #define debug(...) fprintf(stderr, __VA_ARGS__)
- typedef long long LL;
- typedef pair<int, int> pii;
- template<typename T> inline bool chkmax(T &a, const T &b) { return a <b ? a = b, 1 : 0; }
- template<typename T> inline bool chkmin(T &a, const T &b) { return a> b ? a = b, 1 : 0; }
- inline int read() {
- int sum = 0, fg = 1; char c = getchar();
- for (; !isdigit(c); c = getchar()) if (c == '-') fg = -1;
- for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
- return fg * sum;
- }
- const int maxn = 2e3 + 10;
- int Begin[maxn], Next[maxn << 1], To[maxn << 1], w[maxn << 1], e;
- inline void link(int x, int y, int z) { To[++e] = y, Next[e] = Begin[x], Begin[x] = e, w[e] = z; }
- int n, m, sz[maxn];
- LL dp[maxn][maxn];
- inline void dfs(int now, int f) {
- int lim = 1;
- for (int i = Begin[now]; i; i = Next[i]) {
- int son = To[i];
- if (son == f) continue;
- dfs(son, now);
- for (int j = min(lim, m); ~j; j--)
- for (int k = min(sz[son], m); ~k; k--)
- if (j + k <= m)
- chkmax(dp[now][j + k], dp[now][j] + dp[son][k] + (LL) w[i] * (k * (m - k) + (sz[son] - k) * (n - m - sz[son] + k)));
- lim += sz[son];
- }
- sz[now] = lim;
- }
- int main() {
- #ifdef xunzhen
- freopen("tree.in", "r", stdin);
- freopen("tree.out", "w", stdout);
- #endif
- n = read(), m = read();
- chkmin(m, n - m);
- for (int i = 1; i < n; i++) {
- int x = read(), y = read(), z = read();
- link(x, y, z), link(y, x, z);
- }
- dfs(1, 0);
- printf("%lld\n", dp[1][m]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2956222.html