AcWing 1074. 二叉苹果树(树形dp）

#include<bits/stdc++.h>
using namespace std;
const int N=110,M=N<<1;
int n,m,ne[M],idx,h[N],e[M],w[M];
int f[N][N];
void add(int a,int b,int c){
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int fa){
    for(int i=h[u];~i;i=ne[i]){
        int k=e[i];
        if(k==fa)continue;
        dfs(k,u);
        for(int j=m;j>=1;j--){
            for(int b=0;b<j;b++){
                f[u][j]=max(f[u][j],f[u][j-b-1]+w[i]+f[k][b]);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs(1,-1);
    cout<<f[1][m]<<endl;
}