这个题目给定一棵树，以及树的每个树枝的苹果数量，要求在保留K个树枝的情况下最多能保留多少个苹果
一看就觉得是个树形DP，然后想出 dp[i][j]来表示第i个节点保留j个树枝的最大苹果数，但是在树形过程中，有点难表示转移
后来看了下大神的做法才知道其实可以用背包来模拟 树枝的去留，其实真的是个背包诶，每个子树枝就相当于物品，他占用了多少树枝量，带来多少的收益，就是用背包嘛，于是用树形DP+背包就可以做了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 210
using namespace std;
int u[N],v[N],e[N],nt[N],ft[N];
int dp[N][N];
int cnt;
void add(int a,int b,int val)
{
u[cnt]=a;
v[cnt]=b;
e[cnt]=val;
nt[cnt]=ft[a];
ft[a]=cnt++;
}
int n,k;
int sum[N];
void dfs(int x,int f)
{
sum[x]=;
for (int i=ft[x];i>=;i=nt[i]){
int nx=v[i];
if (nx==f) continue;
dfs(nx,x);
sum[x]+=sum[nx];
for (int j=sum[x];j>=;j--){
for (int w=;w<=sum[nx] && w<j;w++){
dp[x][j]=max(dp[x][j],dp[x][j-w]+dp[nx][w]+e[i]);
}
}
}
}
int main()
{
while (scanf("%d%d",&n,&k)!=EOF)
{
cnt=;
int a,b,c;
memset(ft,-,sizeof ft);
for (int i=;i<n;i++){
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
memset(dp,,sizeof dp);
dfs(,-);
printf("%d\n",dp[][k+]);
}
return ;
}