一道树型DP，不过这道题是按照边来做的，和点略有不同，因为累加的是边的权值，并且取m条边，那对于每个子树而言，它选的边肯定是 min(k,m)，k表示子树中的边数，所以要dfs 找边数。 接下来是树型DP的常用套路了 dp[i][j]表示以i为根选j条边产生的值，状态为 根 与 子树，还需要加上权值。 详情见代码
#include<iostream> #include<cstdio> using namespace std; const int maxn=5005; struct node{ int from,to,ds; }list[maxn*2]; int n,m,ans,s,x,y,z,dp[maxn][maxn],head[maxn]; void add(int x,int y,int z){ list[++s].from=head[x]; list[s].to=y; list[s].ds=z; head[x]=s; } int dfs(int x,int fa){ int ans=0; for (int i=head[x];i;i=list[i].from){ if (list[i].to==fa) continue; ans+=dfs(list[i].to,x)+1; for (int j=min(ans,m);j>=1;j--) for (int k=1;k<=j;k++) dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[list[i].to][k-1]+list[i].ds); } return ans; } int main(){ cin>>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,0); cout<<dp[1][m]; return 0; }