[HAOI 2015] 나무 염색

본제 전송문 트리 dp령 d p u, j dp{u, j} dpu, j는 노드 u가 뿌리인 자수에 jj개의 검은 점이 전체 나무에 있는 공헌으로 아들과 아들이 뿌리인 자수의 검은 점 dp u, j = m a x(d p u, j -k + d p v, k +(m -k) ? l e n +(n -m ͩ(s i z e v-k) ?(s i z e v-k){u, j} = max(dp {u, j-k} + dp {v, k} + (m-k) *k*len+(n-m(시즈 v-k) * (size v-k) + dpu, k} + (m-m(시즈 v-k) * * (size v-k) * * dpu, ju, j: k + dpv, k + k+(m -k)) * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
Code:

#include 
#define maxn 2010
#define int long long
using namespace std;
struct Edge{
	int to, next, len;
}edge[maxn << 1];
int num, head[maxn], size[maxn], dp[maxn][maxn], n, m;

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}

void addedge(int x, int y, int z){ edge[++num] = (Edge){y, head[x], z}, head[x] = num; }

void dfs(int u, int pre){
	for (int i = 2; i <= m; ++i) dp[u][i] = -1;
	size[u] = 1;
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre) dfs(v, u), size[u] += size[v];
	}
	for (int i = head[u]; i; i = edge[i].next){
		int v = edge[i].to;
		if (v != pre){
			int l = edge[i].len;
			for (int j = min(m, size[u]); j >= 0; --j)
				for (int k = 0; k <= min(j, size[v]); ++k)
					if (dp[u][j - k] >= 0)
						dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] + (m - k) * k * l + (size[v] - k) * (n - size[v] - m + k) * l);
		}
	}
}

signed main(){
	n = read(), m = read();
	for (int i = 1; i < n; ++i){
		int x = read(), y = read(), z = read();
		addedge(x, y, z), addedge(y, x, z);
	}
	dfs(1, 0);
	printf("%lld
", dp[1][m]);
	return 0;
}