「树上背包」树上染色

和可怜与超市很像的一道题。

将问题转化为统计每条边的贡献，枚举从两端的子树中选的黑点个数来更新答案即可。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
char buf[1 << 20], *p1 = buf, *p2 = buf;
inline char getc() {
	if (p1 == p2) {
		p1 = buf, p2 = buf + fread(buf, 1, 1 << 20, stdin);
		if (p1 == p2) return EOF;
	}
	return *p1++;
}
inline int read() {
	int s = 0, w = 1;
	char c = getc();
	while (c < '0' || c > '9') { if (c == '-') w = -1; c = getc(); }
	while (c >= '0' && c <= '9') s = s * 10 + c - '0', c = getc();
	return s * w;
}
const int maxn = 2000 + 10;
struct edge {
	int nex, to, w;
	edge() {}
	edge(int a, int b, int c) {
		nex = a, to = b, w = c;
	}
}e[maxn << 1];
int head[maxn], tot;
void Add(int u, int v, int w) {
	e[++tot] = edge(head[u], v, w);
	head[u] = tot;
}
long long dp[maxn][maxn];
int siz[maxn];
int n, m;
void DFS(int u) {
	siz[u] = 1;
	for (int i = head[u]; i; i = e[i].nex) {
		int v = e[i].to, w = e[i].w;
		if (siz[v]) continue;
		DFS(v);
		for (int j = min(m, siz[u]); j >= 0; j--) {
			for (int k = min(m - j, siz[v]); k >= 0; k--) {
				long long tmp = 1LL * w * k * (m - k) + 1LL * w * (siz[v] - k) * (n - m - siz[v] + k);
				dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k] + tmp);
			}
		}		
		siz[u] += siz[v];
	}
}
int main() {
	n = read(), m = read();
	int u, v, w;
	for (int i = 1; i < n; i++) {
		u = read(), v = read(), w = read();
		Add(u, v, w), Add(v, u, w);
	}
	DFS(1);
	return printf("%lld
", dp[1][m]), 0;
}