记录编号	600881	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]树上染色	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.460 s
提交时间	2025-05-20 17:37:35	内存使用	34.44 MiB

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll N=2005;
ll n,k;
struct node{
	ll v,w;
};
vector<node> g[N];
ll siz[N];
ll dp[N][N];
void dfs(ll u,ll fa)
{
	siz[u]=1;
	dp[u][0]=dp[u][1]=0;
	for(ll i=0;i<g[u].size();i++)
	{
		ll v=g[u][i].v,w=g[u][i].w;
		if(v==fa) continue;
		dfs(v,u);
		siz[u]+=siz[v];
		for(ll j=min(k,siz[u]);j>=0;j--)
		{
			for(ll m=0;m<=min(j,siz[v]);m++)
			{
				if(dp[u][j-m]==-1) continue;
				ll val=(m*(k-m)+(siz[v]-m)*(n-k-siz[v]+m))*w;
				dp[u][j]=max(dp[u][j],dp[u][j-m]+dp[v][m]+val);
			}
		}
	}
}
int main()
{
	freopen("haoi2015_t1.in", "r", stdin);
		freopen("haoi2015_t1.out", "w", stdout);
	cin>>n>>k;
	k=min(k,n-k);
	for(ll i=1;i<n;i++)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	} 
	memset(dp,-1,sizeof(dp));
	dfs(1,0);
	cout<<dp[1][k];
	return 0;
}