比赛 2024暑假C班集训D 评测结果 AAAAAAAAAA
题目名称 树上染色 最终得分 100
用户昵称 小金 运行时间 0.125 s
代码语言 C++ 内存使用 5.92 MiB
提交时间 2024-07-13 11:13:25
显示代码纯文本
#include<iostream> 
#include<cstdio>
using namespace std;
const int maxm=2010;
int n,k,tot,h[maxm],v[maxm<<1],ne[maxm<<1],size[maxm];
long long e[maxm<<1],f[maxm][maxm];
void add(int x,int y,long long w)
{
	tot++;
	v[tot]=y;
	e[tot]=w;
	ne[tot]=h[x];
	h[x]=tot;
}
void dfs(int x,int fa)
{
	size[x]=1;
	for(int i=h[x];i;i=ne[i])
    {
		int y=v[i];
		if(y==fa) continue;
		dfs(y,x);
		for(int j=min(size[x],k);j>=0;j--)
        {
			for(int k2=min(size[y],k);k2>=0;k2--)
            {
				long long ans=f[x][j]+f[y][k2]+e[i]*k2*(k-k2)+e[i]*(size[y]-k2)*((n-k)-(size[y]-k2));
				f[x][j+k2]=max(f[x][j+k2],ans);
			}
		}
		size[x]+=size[y];
	}
}
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 a,b;
        long long c;
		scanf("%d%d%lld",&a,&b,&c);
		add(a,b,c);
		add(b,a,c);
	}
	dfs(1,0);
	printf("%lld",f[1][k]);
	return 0;
}