状态表示 f[u][j]:表示所有以u为树根的子树中选，选j条边的最大价值 状态计算 每一棵子树看出一组背包，若需要选择该子树son，则根结点u到子树son的边一定用上，因此能用上的总边数一定减1，总共可以选择j条边时，当前子树son分配的最大边数是j - 1，对于任意一棵子树有
f[u][j] = max(f[u][j], f[u][j - 1 - k] f[son][k] w[i])
代码语言：javascript复制#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;
}
