链接：https://ac.nowcoder.com/acm/problem/50505
来源：牛客网

题目描述

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。
tree.png

输入描述: 

第一行两个数N和Q，N表示树的节点数，Q表示要保留的树枝数量。
接下来N-1行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出描述: 

输出仅一行，表示最多能留住的苹果的数量。

题型：

树形dp

思路：

写出状态转移方程：设dp[i][j]为以i为根节点的子树，保留j个分支可以得到的最大苹果数量
下面的代码可以实现多叉树（包括二叉树）
注意j和k可以范围优化：j:min(需要的边数，目前点上有的边数)-->0
k:0-->min(目前点的目前的儿子上有的边数，j-1)
注意k!=j，因为前面的点与当前点的儿子的点之间的这一条边是必须要连接的，所以可以操作的边最少为0，最多为j-1

代码： 

#include<bits/stdc++.h>
using namespace std;
const int N=1e2+20;
int dp[N][N],sum[N],n,q;//sum:存边数 
struct node{
	int to,value;
};
vector<node>G[N];
void dfs(int x,int fa){
	int son;
	for(int i=0;i<G[x].size();i++){
		son=G[x][i].to;
		if(son==fa) continue;
		dfs(son,x);
		sum[x]+=sum[son]+1;
		for(int j=min(q,sum[x]);j>=0;j--){
			for(int k=0;k<=min(sum[son],j-1);k++){
				dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[son][k]+G[x][i].value);
			}
		}
	}
}

int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n-1;i++){
		int x,y,num;
		scanf("%d %d %d",&x,&y,&num);
		G[x].push_back(node{y,num});
		G[y].push_back(node{x,num});
	}
	dfs(1,0);
	printf("%d\n",dp[1][q]);
	return 0;
}