1、http://acm.timus.ru/problem.aspx?space=1&num=1018
2、题目大意：
给出一棵树，该树有n个结点，每条边都有一定量的苹果，现在要删除其中的一部分分支，使得分支数为m条，求最多可以保留多少苹果。其中1号点始终是树根
分析：要想删除第i条边，那么i边的子边也将随着删除，
我们把每条边的值都保存在结点中，对于一条边有两个结点即父节点和子节点，我们把权值放到子节点中，那么根节点即1点权值是0；
保留m条边即保留m+1个结点
用dp[rt][m]表示以rt为根，保留m个子节点的最大值（如果包括rt这个根节点，那么是m+1个结点）
dp[rt][m]=max(dp[rt][m],dp[rt.left][a]+dp[rt.right][b])+tree[rt].w;
即以rt为根的最大值就等于以rt左孩子为根的a条边和加上以rt右孩子为根的b条边和，最后在加上rt自己本身
所以a+b+1=m
3、AC代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 205
struct node
{int l;int r;int w;
} tree[N];
int v[N][N];
int dp[N][N];
int visit[N];
void build(int rt,int n)
{visit[rt]=1;for(int i=1; i<=n; i++){if(visit[i]==0 && v[rt][i]!=-1){if(tree[rt].l==0)tree[rt].l=i;elsetree[rt].r=i;tree[i].w=v[rt][i];build(i,n);}}
}
int dfs(int rt,int m)
{if(rt==0 || m<=0)return dp[rt][m]=0;if(dp[rt][m]!=-1)return dp[rt][m];dp[rt][m]=0;for(int a=0;a<m;a++){int b=m-a-1;dp[rt][m]=max(dp[rt][m],dfs(tree[rt].l,a)+dfs(tree[rt].r,b));}return dp[rt][m]+=tree[rt].w;
}
int main()
{int n,m,a,b,c;scanf("%d%d",&n,&m);memset(v,-1,sizeof(v));for(int i=0; i<n-1; i++){scanf("%d%d%d",&a,&b,&c);v[a][b]=c;v[b][a]=c;}memset(visit,0,sizeof(visit));memset(tree,0,sizeof(tree));build(1,n);memset(dp,-1,sizeof(dp));dfs(1,m+1);printf("%d\n",dp[1][m+1]);return 0;
}
/*
5 2
1 3 1
1 4 10
2 3 20
3 5 20
*/