令$f[p][i]$表示以$p$为根的子树内，选了$i$个黑点，剩下的都是白点的这个子树内贡献的答案
如果$p$的子树都算出来了，只要计算$p$与$fa[p]$之间的边对答案的贡献就好了，贡献是$dis * (i * (sz - i) + (k - i) * (n - k - (sz - i)))$
于是树形动规一下就好了
1 /************************************************************** 2 Problem: 4033 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:308 ms 7 Memory:32300 kb 8 ****************************************************************/ 9 10 #include <cstdio> 11 #include <cstring> 12 #include <algorithm> 13 14 using namespace std; 15 typedef long long ll; 16 17 const int N = 2e3 + 5; 18 19 struct edge { 20 int next, to, v; 21 edge(int _n = 0, int _t = 0, int _v = 0) : next(_n), to(_t), v(_v) {} 22 } e[N << 1]; 23 24 int n, k; 25 int first[N], tot; 26 int sz[N]; 27 ll f[N][N], tmp[N]; 28 29 inline void Add_Edges(int x, int y, int z) { 30 e[++tot] = edge(first[x], y, z), first[x] = tot; 31 e[++tot] = edge(first[y], x, z), first[y] = tot; 32 } 33 34 inline ll calc(int x, int y) { 35 return 1ll * y * (x - y); 36 } 37 38 #define y e[x].to 39 inline void dfs(int p, int fa, int w) { 40 int x, i, j; 41 sz[p] = 1; 42 for (x = first[p]; x; x = e[x].next) 43 if (y != fa) { 44 dfs(y, p, e[x].v); 45 memcpy(tmp, f[p], sizeof(tmp)); 46 for (i = min(sz[p], k); ~i; --i) 47 for (j = min(sz[y], k - i); ~j; --j) 48 tmp[i + j] = max(tmp[i + j], f[p][i] + f[y][j]); 49 memcpy(f[p], tmp, sizeof(tmp)); 50 sz[p] += sz[y]; 51 } 52 for (i = min(sz[p], k); ~i; --i) 53 f[p][i] += (calc(k, i) + calc(n - k, sz[p] - i)) * w; 54 } 55 #undef y 56 57 int main() { 58 int i, x, y, z; 59 scanf("%d%d", &n, &k); 60 for (i = 1; i < n; ++i) { 61 scanf("%d%d%d", &x, &y, &z); 62 Add_Edges(x, y, z); 63 } 64 dfs(1, 0, 0); 65 printf("%lld ", f[1][k]); 66 return 0; 67 }