P2015 二叉苹果树

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
const int maxn=105;
using namespace std;
int n,m,ff[maxn][maxn];
struct b{
    int to;
    int ne;
    int w;    
}e[maxn*2];
int p;
int head[maxn];
void add(int f,int to,int w){
    p++;
    e[p].ne=head[f];
    e[p].to=to;
    e[p].w=w;
    head[f]=p;
}
int x,y,z;
int son[maxn];
void dfs(int now,int f){
    for(int i=head[now];i;i=e[i].ne){
        int v=e[i].to;
            if(v==f) continue;
        dfs(v,now);
        son[now]+=son[v]+1;
        for(int j=min(son[now],m);j;--j ){//我们就能取这些了
            for(int k=min(son[v],j-1);k>=0;k--){//考虑一下怎么分配要保留的边
                ff[now][j]=max(ff[now][j],ff[now][j-k-1]+ff[v][k]+e[i].w);//记得减一，不然我们就和这个v断开了联系
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;++i){
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
        add(y,x,z);
    }
    dfs(1,-1);//根节点是谁不重要
    printf("%d",ff[1][m]);
    return 0;
}