题目描述
有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）
这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。
我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树
2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。
给定需要保留的树枝数量，求出最多能留住多少苹果。
输入输出格式
输入格式：第1行2个数，N和Q(1<=Q<= N,1<N<=100)。
N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。
每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。
每根树枝上的苹果不超过30000个。
输出格式：一个数，最多能留住的苹果的数量。
输入输出样例
输入样例#1：
5 21 3 11 4 102 3 203 5 20
输出样例#1：
21
这是一道比较不错的树形DP的题目， 刚开始的时候用贪心乱搞，搞了搞边，搞了搞点，搞了颗树，搞了39分。。。 
贪心
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int MAXN=1001; 7 int n,q; 8 int v[MAXN]; 9 int vis[MAXN]; 10 int deep[MAXN]; 11 int read(int & n) 12 { 13 char p='+';int x=0; 14 while(p<'0'||p>'9') 15 p=getchar(); 16 while(p>='0'&&p<='9') 17 x=x*10+p-48,p=getchar(); 18 n=x; 19 } 20 struct node 21 { 22 int u; 23 int v; 24 int w; 25 int nxt; 26 }edge[MAXN]; 27 int num=1; 28 int head[MAXN]; 29 void add_edge(int x,int y,int z) 30 { 31 edge[num].u=x; 32 edge[num].v=y; 33 edge[num].w=z; 34 edge[num].nxt=head[x]; 35 head[x]=num++; 36 } 37 struct deal 38 { 39 int how; 40 int val; 41 int l; 42 }a[MAXN]; 43 void build_tree(int p) 44 { 45 vis[p]=1; 46 for(int i=head[p];i!=-1;i=edge[i].nxt) 47 { 48 if(vis[edge[i].v]==0) 49 { 50 deep[edge[i].v]=deep[p]+1; 51 build_tree(edge[i].v); 52 } 53 54 } 55 } 56 void deal_val(int p,int pre) 57 { 58 vis[p]=1; 59 for(int i=head[p];i!=-1;i=edge[i].nxt) 60 { 61 int will=edge[i].v; 62 if(will!=0&&vis[will]==0&&deep[will]>deep[p]) 63 { 64 a[pre].l++; 65 a[pre].val+=edge[i].w; 66 deal_val(will,pre); 67 } 68 69 70 } 71 } 72 int comp(const deal & a ,const deal & b) 73 { 74 if(a.val!=b.val) 75 return a.val
后来看题解用树形DP，
对于每一个节点，我们可以枚举它相连的边，
用dp[i][j]表示第i个节点，在他的子节点中保留j条树枝的最大值
那么我们可以枚举节点和j，当然，在枚举j的时候我们需要同时枚举一个k
我们可以想一下，该节点i需要保留j条边，那么我们取他的最大值得时候，可以对他相连的节点进行DP，
如果j=5，这时候需要保留5条边，
因为整个树是二叉树，所以说，他的相连的一条边所能删除的最大数就是4（相连的线段一定会删除）
那么k的范围：0--4
动态转移方程：
dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[will][k]+edge[i].w);
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 const int MAXN=1001; 7 int n,q; 8 int v[MAXN]; 9 int vis[MAXN];10 int deep[MAXN];11 int dp[MAXN][MAXN];12 int read(int & n)13 {14 char p='+';int x=0;15 while(p<'0'||p>'9')16 p=getchar();17 while(p>='0'&&p<='9')18 x=x*10+p-48,p=getchar();19 n=x;20 }21 struct node22 {23 int u;24 int v;25 int w;26 int nxt;27 }edge[MAXN];28 int num=1;29 int head[MAXN];30 void add_edge(int x,int y,int z)31 {32 edge[num].u=x;33 edge[num].v=y;34 edge[num].w=z;35 edge[num].nxt=head[x];36 head[x]=num++;37 }38 int dfs(int u,int fa)39 {40 int ans=0;41 for(int i=head[u];i!=-1;i=edge[i].nxt)42 {43 int will=edge[i].v;44 if(will==fa)45 continue;46 ans+=dfs(will,u)+1;47 for(int j=min(q,ans);j>=1;j--)48 {49 for(int k=min(j,ans)-1;k>=0;k--)50 {51 dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[will][k]+edge[i].w);52 }53 }54 }55 return ans; 56 }57 int main()58 {59 read(n);read(q);60 for(int i=1;i<=n;i++)61 head[i]=-1;62 for(int i=1;i<=n-1;i++)63 {64 int x,y,z;65 read(x);read(y);read(z);66 add_edge(x,y,z);67 add_edge(y,x,z);68 }69 dfs(1,0);70 cout<