题目大概说一棵n结点二叉苹果树，n-1个分支，每个分支各有苹果，1是根，要删掉若干个分支，保留q个分支，问最多能保留几个苹果。
挺简单的树形DP，因为是二叉树，都不需要树上背包什么的。
- dp[u][k]表示以u结点为根的子树保留k个分支最多能有的苹果数
- 转移就是左子树若干个，右子树若干个转移。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 111
struct Edge{
int v,w,next;
}edge[MAXN<<];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].v=v; edge[NE].w=w; edge[NE].next=head[u];
head[u]=NE++;
}
int n,q,d[MAXN][MAXN];
void dp(int u,int fa){
d[u][]=;
int lson=-,rson=-,w1,w2;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
if(v==fa) continue;
if(lson==-) lson=v,w1=edge[i].w;
else rson=v,w2=edge[i].w;
dp(v,u);
}
if(lson==-) return;
if(rson==-){
for(int i=; i<q; ++i){
if(d[lson][i]==-) continue;
d[u][i+]=max(d[u][i+],d[lson][i]+w1);
}
return;
}
for(int i=; i<=q; ++i){
if(d[lson][i]==-) continue;
for(int j=; j<=q-i; ++j){
if(d[rson][j]==-) continue;
if(i+j+<=q) d[u][i+j+]=max(d[u][i+j+],d[lson][i]+d[rson][j]+w1+w2);
if(i== && j+<=q) d[u][j+]=max(d[u][j+],d[rson][j]+w2);
if(j== && i+<=q) d[u][i+]=max(d[u][i+],d[lson][i]+w1);
}
}
}
int main(){
int a,b,c;
while(~scanf("%d%d",&n,&q)){
NE=;
memset(head,-,sizeof(head));
for(int i=; i<n; ++i){
scanf("%d%d%d",&a,&b,&c);
addEdge(a,b,c);
addEdge(b,a,c);
}
memset(d,-,sizeof(d));
dp(,);
printf("%d\n",d[][q]);
}
return ;
}