比赛 |
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;
}