题目链接：Click here
Solution:
设\(f[i][j]\)表示以\(i\)为根的子树保留\(j\)条边的最大值
得到转移式：\(f[i][j]=max(f[i][j],f[i][j-k-1]+f[son_i][k]+val[i][son_i])\)
用vector来存每个点的儿子，倒着转移即可，时间复杂度\(O(n^3)\)
Code:
//Luogu P2015 Tree dp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=101;
int n,m,cnt,head[N];
int sz[N],f[N][N],val[N];
vector<int> q[N];
struct Edge{int nxt,to,val;}edge[N<<1];
void ins(int x,int y,int z){
edge[++cnt].nxt=head[x];
edge[cnt].to=y;head[x]=cnt;
edge[cnt].val=z;
}
void dfs(int x,int fa){
for(int i=head[x];i;i=edge[i].nxt){
int y=edge[i].to;
if(y==fa) continue;
dfs(y,x);sz[x]+=sz[y];
q[x].push_back(y);
val[y]=edge[i].val;
}sz[x]++;
for(int j=0;j<q[x].size();j++)
for(int i=min(sz[x]-1,m);i;i--)
for(int k=i-1;k>=0;k--)
f[x][i]=max(f[x][i],f[x][i-1-k]+f[q[x][j]][k]+val[q[x][j]]);
}
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
signed main(){
n=read();m=read();
for(int i=1;i<n;i++){
int x=read(),y=read(),z=read();
ins(x,y,z),ins(y,x,z);
}dfs(1,0);printf("%d\n",f[1][m]);
return 0;
}