1 #include <bits/stdc++.h> 2  3 using namespace std; 4 #define inf 0x3f3f3f3f 5 #define M 5000 6 int next[M],pre[M],last[M],apple[M],dp[M][M],n,m,tot=0; 7 /* 8 dp[i][j]表示节点i保留j个枝条的所剩苹果最大值 9 apple[i]表示第i条边上的苹果数10 next,pre,last是用来建边的数组11 tot来统计边的序号12 */13 void cnct (int u,int v,int w)14 {15     tot++;16     next[tot]=v;17     pre[tot]=last[u];18     last[u]=tot;19     apple[tot]=w;20 }21 int dfs (int u,int father)22 {23     int ans=0;//ans表示u节点的子节点数目24     for (int i=last[u];i!=0;i=pre[i])25     {26         int v=next[i],value=http://www.mamicode.com/apple[i];27         if(v == father)continue;//如果下一个相邻节点就是父节点，则证明到底层了，开始递归父节点的兄弟节点28         ans+=dfs(v,u)+1;//递归到最上层的根节点129         for(int j=min(ans,m);j>=1;--j)//因为有限制枝条的数目，取个min30         {31             for(int k=min(j,ans);k>=1;--k)32             dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k-1]+value);33 /*34 对于u节点下的子节点j，对j保留多少枝条最优进行dp35 在这里好好说明下，因为建树是我们是按照递归建的树。36 进行比较时，dp[u][j]都是前面选择除i外的子节点得到的最优解结果37 所以dp的时候不可能重复或者漏掉某节点38 */39         }40     }41     return ans;42 }43 int main()44 {45     //freopen("de.txt","r",stdin);46     memset(last,0,sizeof last);47     memset(next,0,sizeof next);48     memset(pre,0,sizeof pre);49     memset(dp,0,sizeof dp);50     scanf("%d%d",&n,&m);51     for(int i=1;i<n;++i)52     {53         int x,y,value;54         scanf("%d%d%d",&x,&y,&value);55         cnct(x,y,value);56         cnct(y,x,value);57     }58     dfs(1,0);59     printf("%d\n",dp[1][m]);60     return 0;61 }62