#include<bits/stdc++.h> using namespace std; #define ll long long int const N=1e2+7; int const M=1e2+7; int n,m; struct node{ int a,next,len; }e[M<<1]; int cnt,head[N]; void add(int x,int y,int len){ e[++cnt].a=y; e[cnt].len=len; e[cnt].next=head[x]; head[x]=cnt; } ll f[N][M]; void dfs(int x,int fa){ for(int i=head[x];i;i=e[i].next){ int v=e[i].a; if(v==fa) continue; dfs(v,x); //枚举右子树 //也可以看成背包中的枚举物品 //枚举右子树的根并且预处理右子树 for(int j=m;j>=1;--j){ //可以看成背包中的枚举体积 for(int k=0;k<=j-1;++k){ //右子树保留的边数 //枚举物品v的体积 f[x][j]=max(f[x][j],f[x][j-k-1]+f[v][k]+e[i].len); //在这里以v为根的右子树为已知条件,所以f[x][k]为转移f[x][j]的前驱,为避免错误,所以j倒着枚举 ,背包一般都是j倒着枚举 //k为物品体积,f[v][k]+len为物品价值 //背包一般都省略了一维i,在考虑是否倒着循环,要考虑i } } } } int main(){ cin >> n >> m; for(int i=1,a,b,c;i<=n-1;++i){ cin >> a >> b >> c; add(a,b,c);add(b,a,c); } dfs(1,1); cout << f[1][m]; return 0; }