solution-code4575

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define LL long long
6
using namespace std;
7
struct Node
8
{
9
  int to,next,val;
10
}e[4005];
11
LL f[2005][2005],tmp[2005];
12
int n,m,siz[2005],h[2005],cnt;
13
inline void Addedge(int x,int y,int v)
14
{
15
  e[++cnt]=(Node){y,h[x],v};h[x]=cnt;return;
16
}
17
inline void DP(int x,int pre)
18
{
19
  int i,j,k,y;
20
  siz[x]=1;
21
  for(i=h[x];i;i=e[i].next)
22
  {
23
    y=e[i].to;
24
    if(y==pre)continue;
25
    DP(y,x);
26
    memset(tmp,0,sizeof(tmp));
27
    for(j=0;j<=siz[x];++j)
28
    {
29
      for(k=0;k<=siz[y];++k)
30
      {
31
        if(j+k>m)break;
32
        LL t=1LL*e[i].val*(1LL*(m-k)*k+1LL*(siz[y]-k)*(n-siz[y]-(m-k)));
33
        tmp[j+k]=max(tmp[j+k],f[x][j]+f[y][k]+t);
34
      }
35
    }
36
    siz[x]+=siz[y];
37
    for(j=0;j<=siz[x];++j)f[x][j]=tmp[j];
38
  }
39
  return;
40
}
41
int main(void)
42
{
43
  int i,x,y,v;
44
  scanf("%d%d",&n,&m);
45
  for(i=1;i<n;++i)
46
  {
47
    scanf("%d%d%d",&x,&y,&v);
48
    Addedge(x,y,v);
49
    Addedge(y,x,v);
50
  }
51
  DP(1,0);
52
  printf("%lld\n",f[1][m]);
53
  return 0;
54
}