Pre
想不出来,不得不说这套路还不错。
调试代码到了最后发现有一个地方 \(u\) 写成了 \(to[i]\)
Solution
考虑每一条边的贡献。
\(w=w_i*cntblack_{left}*cntblack_{right}+w_i*cntwhite_{left}*cntwhite_{right}\)
以这个等式进行 \(DP\)
最终计算答案。
Code
#include <cstdio>
#include <cstring>
#include <limits.h>
#define ll long long
using namespace std;
inline ll min (ll u, ll v) { return u > v ? v : u;}
inline ll max (ll u, ll v) { return u > v ? u : v;}
const int N = 2000 + 5;
int n, k;
int fr[N << 1], to[N << 1], h[N], tot, sz[N];
ll val[N << 1], dp[N][N];
inline void dfs (int u, int f) {
memset (dp[u], -1, sizeof dp[u]);
dp[u][0] = dp[u][1] = 0;
sz[u] = 1;
for (int i = h[u]; i; i = fr[i]) {
if (to[i] == f) continue;
dfs (to[i], u);
sz[u] += sz[to[i]];
}
for (int i = h[u]; i; i = fr[i]) {
if (to[i] == f) continue;
for (int c = min (k, sz[u]); c >= 0; --c) {
for (int j = 0; j <= min (c, sz[to[i]]); ++j) {
if (~dp[u][c - j])
dp[u][c] = max (dp[u][c], dp[u][c - j] + dp[to[i]][j] + val[i] * j * (k - j) + val[i] * (sz[to[i]] - j) * (n - k + j - sz[to[i]]));
}
}
}
}
inline void add (int u, int v, ll w) {
tot++;
fr[tot] = h[u];
to[tot] = v;
h[u] = tot;
val[tot] = w;
}
int main () {
#ifdef chitongz
freopen ("x.in", "r", stdin);
#endif
scanf ("%d%d", &n, &k);
for (int i = 1; i < n; ++i) {
int x, y; ll z;
scanf ("%d%d%lld", &x, &y, &z);
add (x, y, z); add (y, x, z);
}
dfs (1, 0);
printf ("%lld\n", dp[1][k]);
return 0;
}
Conclusion
尝试换一个方向思考。