原题链接：https://ac.nowcoder.com/acm/problem/50505

题目大意：

有一棵二叉苹果树，如果数字有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共N个节点，标号1至N，树根编号一定为1。
我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵有四根树枝的苹果树，因为树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

解题思路：

一个二维数组的dp，记录第i个节点往下包括j个节点的最大值，递推公式：遍历的时候i要从大往小。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
typedef complex <double> cp;
#define debug(a) cout<<#a<<":"<<a<<endl;
#define fr freopen("in.txt","r",stdin);
#define Fill(x,a) memset(x,a,sizeof(x))
#define cpy(a,b) memcpy(a,b,sizeof(a))
const double PI = acos(-1);
const int INF=0x3f3f3f3f;
const int N=1e6+7;
const int mod=1e9+7;
int maxn,minn;
int T,n,m,q;
struct aa{
    int u,w,next;
}edge[N];
int head[N];
int cnt;
int dp[500][500];

void init(){
    cnt=1;
    Fill(head,0);
    return ;
}

void add(int u,int v,int w){
    edge[cnt].next=head[u];
    edge[cnt].u=v;
    edge[cnt].w=w;
    head[u]=cnt++;
    return ;
}


void dfs(int u,int p){
    int v,w;
    for(int i=head[u];i!=0;i=edge[i].next){
        v=edge[i].u;
        w=edge[i].w;
        if(v==p)    continue;
        dfs(v,u);
        for(int i=m;i>=1;i--){
            for(int j=1;j<=i;j++){
                dp[u][i]=max(dp[u][i],dp[v][j-1]+dp[u][i-j]+w);    
            }
        }
    }

}

int main(){
    int u,v,w;
    cin>>n>>m;
    init();
    for(int i=1;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        add(u,v,w);
        add(v,u,w);
    }
    dfs(1,0);
//    for(int i=1;i<=n;i++){
//        for(int j=0;j<=m;j++){
//            cout<<dp[i][j]<<" ";
//        }
//        cout<<endl;
//    }
    for(int i=1;i<=m;i++){
        maxn=max(dp[1][i],maxn);
    }
    cout<<maxn<<endl;



    return 0;
}