二叉苹果树

描述

有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）。
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N，树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝
的树：
2 5
＼／
3 4
＼／
1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量，求出最多能留住多少苹果。注意树根不能剪没了哟。

输入

第1行2个数，N和Q(1<=Q<=N，I<N<=IOO)。
N表示树的结点数，Q表示要保留的树枝数量。
接下来N-I行描述树枝的信息。每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。每根树枝上的苹果不超过30000个。

输出

一个数，最多能留住的苹果的数量。

样例

输入

输出

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,head[10001],tot,f[1001][1001],q,root=1,edge[10001],use[10001];
 4 struct data {
 5     int to,nxt,val;
 6 } e[10001];
 7 void build(int x,int y,int z) {
 8     e[++tot].to=y;
 9     e[tot].val=z;
10     e[tot].nxt=head[x];
11     head[x]=tot;
12 }
13 void dp(int x) {
14     use[x]=1;
15     for(int i=head[x]; i; i=e[i].nxt) {
16         int v=e[i].to;
17         if(use[v])
18             continue;
19         dp(v);
20         edge[x]+=edge[v]+1;
21         for(int p=min(q,edge[x]); p>=1; p--)
22             for(int k=min(edge[v],p-1); k>=0; k--)
23                 f[x][p]=max(f[x][p-k-1]+e[i].val+f[v][k],f[x][p]);
24     }
25 }
26 int main() {
27     scanf("%d%d",&n,&q);
28     for(int i=1; i<=n-1; i++) {
29         int x,y,z;
30         scanf("%d%d%d",&x,&y,&z);
31         build(x,y,z);
32         build(y,x,z);
33     }
34     dp(root);
35     printf("%d
",f[root][q]);
36     return 0;
37 }