树上背包（新模板 & 理解3）

#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;
}