设想苹果树很象二叉树，每一枝都是生出两个分支。我们用自然数来数这些枝和根那么必须区分不同的枝（结点），假定树根编号都是定为1，并且所用的自然数为1到N。N为所有根和枝的总数。例如下图的N为5，它是有4条枝的树。
2 5
\ /
3 4
\ /
1
当一棵树太多枝条时，采摘苹果是不方便的，这就是为什么有些枝要剪掉的原因。现在我们关心的是，剪枝时，如何令到损
失的苹果最少。给定苹果树上每条枝的苹果数目，及必须保留的树枝的数目。你的任务是计算剪枝后，能保留多少苹果。
input：
首行为N，Q (1 <= Q <= N, 1 < N <= 100), N为一棵树上的根和枝的编号总数，Q为要保留的树枝的数目。以下N-1行
为每条树枝的描述，用3个空格隔开的整数表示，前2个数为树枝两端的编号,第三个数为该枝上的苹果数。假设每条枝上的苹
果数不超过3000个。
output:
输出能保留的苹果数。（剪枝时，千万不要连根拔起哦）。
分析：
这道题,可以马上看出是树形Dp,f[i,j]表示以i为根的子树(还包括 [i与 i的父亲] 这条边)内,保存j条
边最多可以有多少苹果,显然f[i,j]=max(f[left[i],k]+f[right[i],j-k-1])+apple[i];
【参考程序】：
#include<iostream>
using namespace std;
struct node
{
int lc,rc;
int s;
} tree[101];
//i-j相连的数量。//i为节点留j条枝的最优值。
int apple[101][101],f[101][101];
bool v[101];//访问标志。
int n,q;
void dfs(int k)
{
v[k]=false;
for (int i=1;i<=n;i++)
if (v[i] && apple[k][i]!=-1)
{//没有访问且与父亲相连。
if (tree[k].lc==0) tree[k].lc=i;
else tree[k].rc=i;//任意的，这里谁左右没关系，其实只是为了建树。
tree[i].s=apple[k][i];//孩子继承父亲，为后面dp搜素做准备。
dfs(i);
}
}
int dp_max(int t,int k)
{
if (f[t][k]!=-1) return f[t][k];//因为是自底向上dp，前面的必定最优。
if (t==0 || k==0)
{//分的枝条已经没有或已经是叶子节点。
f[t][k]=0;return 0;
}
f[t][k]=0;
for (int i=0;i<=k-1;i++)
{//枚举左右孩子各取多少枝条所达到的最优值。
int ls=dp_max(tree[t].lc,i);
int rs=dp_max(tree[t].rc,k-1-i);
if (f[t][k]<ls+rs) f[t][k]=ls+rs;
}
f[t][k]+=tree[t].s;//返回时父亲也要算。
return f[t][k];
}
int main()
{
scanf("%d%d",&n,&q);
memset(apple,-1,sizeof(apple));
int a,b,c;
for (int i=2;i<=n;i++)
{
scanf("%d%d%d",&a,&b,&c);
apple[a][b]=c;apple[b][a]=c;
}
memset(v,true,sizeof(v));
memset(tree,0,sizeof(tree));
dfs(1);
memset(f,-1,sizeof(f));
int ans=dp_max(1,q+1);
printf("%d\n",ans);
return 0;
}