来康康蒟蒻修改了整整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;
}

超级好看的程序

#include<iostream>
using namespace std;
int f[105][105],map[105][105],apple[30001],leftson[30001],rightson[30001];
int n,Q;
void root(int Root)//端点Root 
{
	for(int i=1;i<=n;i++)
	{
		if(map[Root][i]>=0)//寻找左孩子 
		{
			apple[i]=map[Root][i];//存左孩子的树枝的果子数 
			leftson[Root]=i; //记录Root的左孩子为i 
			map[Root][i]=-1;// 不能用啦 
			map[i][Root]=-1;// 不能用啦 
			root(i);//左孩子成为左孩子树的根节点 
			break;
		}
	}
		for(int i=1;i<=n;i++)
	{
		if(map[Root][i]>=0)//寻找右孩子 
		{
			apple[i]=map[Root][i];//存右孩子的树枝的果子数 
			rightson[Root]=i;//记录Root的右孩子为i 
			map[Root][i]=-1;// 不能用啦 
			map[i][Root]=-1;// 不能用啦 
			root(i);//右孩子成为右孩子树的根节点 
			break;
		}
	}
 } 
int s(int Address,int Point)//寻找端点Address 上有Point个节点的最大值 
{
	
	if(f[Address][Point]==-1) //记忆化搜索 
	{
		int max1=-2;
		for(int i=0;i<=Point-1;i++)
		{
			max1=max(max1,s(leftson[Address],i)+s(rightson[Address],Point-i-1)+apple[Address]); //动态转移方程！ 
		}
		f[Address][Point]=max1;
	}
//	cout<<Address<<' '<<Point<<' '<<f[Address][Point];
	return f[Address][Point];
}
int main()
{
	int a,b,c;
	
	cin>>n>>Q;
	for(int i=1;i<=101;i++)
	{
		for(int j=1;j<=101;j++)
		{
			f[i][j]=map[j][i]=-1;
		}
	}//初始化50% 
	for(int i=1;i<=n-1;i++)
	{
		cin>>a>>b>>c;
		map[a][b]=c;
		map[b][a]=c;
	}//输入 
	root(1);//构造二叉树  1一定是根节点 
	for(int i=1;i<=n;i++)
	{
		if(leftson[i]==0&&rightson[i]==0) 
		for(int j=1;j<=Q;j++)
		f[i][j]=apple[i];//没有左右孩子的节点的最大值 都是 他自己的树枝的苹果数 
	} //初始化100% 

	f[1][Q+1]=s(1,Q+1);//开始动态规划 
	cout<<f[1][Q+1];//Finish !
}