描述
有一棵苹果树，如果树枝有分叉，一定是分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个。
输出
一个数，最多能留住的苹果的数量。
样例
输入
5 2 1 3 1 1 4 10 3 2 20 3 5 20
输出
21
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\n",f[root][q]); 36 return 0; 37 }