来康康蒟蒻修改了整整4天der代码：

@ S.H.Z.宋昊哲 (2023songhaozhe) @ 李书航 (2023lishuhang) @ 陆月乄雪 (2023liyanxing) @ f(x)=Asin(ωx+φ) (2316wangshichang) @ 夜莺 (2022lidongran) @ 郭家昊 (2022guojiahao)

#include<cstdio>
#include<cmath>
using namespace std;

int n, q;

int const N=1e2+1;
int tree[N][N];  //临时存储 输入 树 数据 

int left[N];  //存储 结点i 的左子树 
int right[N];  //存储 结点i 的右子树 
int apple[N];  //存储 结点i 的苹果数量 

int dp[N][N];

void build(int v){  //建树 过程  v：根结点 
	/* !!!WARNING: 由于含有 break ，两个 for 循环 不能合并 */
	//左子树
	for(int i=1; i<=n; i++){  //循环遍历 结点 [1, n]
		if(tree[v][i] >= 0){  //tree[v][i] 未被读取 
			left[v] = i;  //建立 根v 与左子树i 的连接关系 
			apple[i] = tree[v][i];  //存储 结点i 的苹果数量 
			
			tree[v][i] = tree[i][v] = -1;  //标记 tree[v][i]、tree[i][v] 已读取
			
			build(i);  //以 i 为根，继续 建树 
			
			break;	//根v 已匹配到相应的 左子树，退出循环 
		}	
	}
	
	//右子树
	for(int i=1; i<=n; i++){  //循环遍历 结点 [1, n]
		if(tree[v][i] >= 0){  //tree[v][i] 未被读取
			right[v] = i;  //建立 根v 与右子树i 的连接关系 
			apple[i] = tree[v][i];  //存储 结点i 的苹果数量 
			
			tree[v][i] = tree[i][v] = -1;  //标记 tree[v][i]、tree[i][v] 已读取
			
			build(i);  //以 i 为根，继续 建树
			
			break;	//根v 已匹配到相应的 右子树，退出循环
		}		
	}
	
	return ;
}

int TreeDP(int l, int r){  //动态规划 过程    l：区间左端点（即 当前结点）  r：区间右端点（即 剩余可剪枝的数目） 
	if(!r) return 0;  //递归结束条件：区间右端点（剩余可剪枝的数目）为 0，即 已剪枝的数目==q，结束递归
	
	if(!left[l] && !right[l]) return apple[l];  //当前结点无子树，说明 当前结点为叶子结点，返回 当前结点 的苹果数量
	if(dp[l][r]) return dp[l][r];  //dp[l][r] 已存入数据，直接返回 dp[l][r]
	
	for(int k=0; k<r; k++) dp[l][r] = fmax(dp[l][r], TreeDP(left[l], k)+TreeDP(right[l], r-k-1)+apple[l]);  //状态转移方程 
		
	return dp[l][r];  //返回 dp[l][r]，即 最优方案 
}            

int main(){
	//输入  
	scanf("%d%d", &n, &q);
	
	//初始化，防止输入时 出现 x == 0 的情况【偷偷说，somebody 被这个 0 坑惨了。。】 
    //P.S. 感谢 李书航 提供的洛谷数据下载机会~~
	for(int i=1; i<=n; i++){
		for(int j=1; j<=n; j++) tree[i][j] = -1;  //初始化 数组 tree 数据为 -1 
	}
	
	for(int i=1; i<n; i++){
		int f, t, x;
		scanf("%d%d%d", &f, &t, &x);
		
		tree[f][t] = x;
	} 
	
	build(1);  //以 1（根结点） 为根，进行 建树
	
	int max_apple=TreeDP(1, q+1);  //树型动态规划，实质：区间型动态规划
	printf("%d\n", max_apple);  //输出  最优方案（dp[1][q+1]）  

    return 0;
}