二叉苹果树

5 2
1 3 1
1 4 10
2 3 20
3 5 20

21

 #include<iostream>
 #include<algorithm>
 #include<cstring>
 using namespace std;
 const int N=105,M=2*N;
 int h[N],ne[M],w[M],e[M],idx;
 int n,m;
 int dp[N][N];
 void add(int x,int y,int z){
     e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
 }
 void dfs(int u,int f){
     for(int i=h[u];~i;i=ne[i]){
         int s=e[i];
         if(s==f)continue;
         dfs(s,u);
         //j代表以u为根节点且当前可保留的树枝数
         for(int j=m;j>=0;j--){
             //k代表以u为根节点的子树可用于保留的树枝树，
             //由于如果要保留子树，则必须保留保留根节点到子树的一条边，所以子树最多能够使用的边为j-1
             for(int k=0;k<=j-1;k++){
                 dp[u][j]=max(dp[u][j],dp[s][k]+dp[u][j-k-1]+w[i]);
             }
         }
     }
 }
 int main(){
     cin>>n>>m;
     memset(h,-1,sizeof h);
     for(int i=0;i<n-1;i++){
         int x,y,z;
         cin>>x>>y>>z;
         add(x,y,z);
         add(y,x,z);
     }
     dfs(1,-1);
     cout<<dp[1][m]<<endl;
     return 0;
 }