记录编号	576636	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.420 s
提交时间	2022-10-14 09:29:17	内存使用	37.36 MiB

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
typedef long long ll;
const ll INF = 1e16;

int head[maxn],ver[maxn << 1],nxt[maxn << 1],dis[maxn << 1],cnt;
void add(int u,int v,int t) {
	ver[++ cnt] = v;
	nxt[cnt] = head[u];
	head[u] = cnt;
	dis[cnt] = t;
	return ;
} 

int n,k;
ll f[maxn][maxn];
int sz[maxn];

void dfs(int u,int fa) {
	sz[u] = 1;
	f[u][0] = f[u][1] = 0;
	for(int i = head[u];i;i = nxt[i]) {
		int v = ver[i],w = dis[i];
		if(v == fa)continue ;
		dfs(v , u);
		sz[u] += sz[v];
		for(int j = std::min(sz[u] , k);~ j;-- j) {
			for(int q = 0;q <= std::min(sz[v] , j);++ q) {
				f[u][j] = std::max(f[u][j] , f[u][j - q] + f[v][q] + 1ll * w * q * (k - q) + 1ll * w * (sz[v] - q) * (n - k - (sz[v] - q)));
			}
		}
	}
	return ;
}

int main() {
	freopen("haoi2015_t1.in","r",stdin);
	freopen("haoi2015_t1.out","w",stdout);
	scanf("%d %d",&n,&k);
	for(int i = 1;i < n;++ i) {
		int u,v,t;
		scanf("%d %d %d",&u,&v,&t);
		add(u , v , t);
		add(v , u , t);
	}
	
	for(int i = 1;i <= n;++ i)
		for(int j = 0;j <= k;++ j)f[i][j] = -INF;
	
	dfs(1 , 0);
	printf("%lld\n",f[1][k]);
	return 0;
}