树形dp，一般用dfs辅助解决。
当我们搜索到\(u\)，此时剩下\(cnt\)条边可以用，也就是说\(u\)为根节点的子树最多可以保留\(cnt\)条边。
由于上一层的需求，我们显然需要枚举剩余边数\(i\)（\(1\leq i\leq cnt\)）。接下来对于每个\(i\)，我们考虑剩余的\(u\)条边可以怎么放。
- 只分配给左边，那么连接左子树用去\(1\)条边，左子树实际有\(i-1\)条边可以用。
- 只分配给右边，那么连接右子树用去\(1\)条边，右子树实际有\(i-1\)条边可以用。
- 两边都分配，枚举左子树分配多少条边，用\(j\)表示，那么连接左右子树用去\(2\)条边，右子树实际有\(i-j-2\)条边可以用（\(0\leq j\leq i-2\)）。你可能会疑惑，\(j=0\)也算分配给左子树吗？因为我们已经拿出\(2\)条边来连接左右子树了，所以尽管左子树没有边可用，这与第②条也是不一样的。
边界条件就是叶子节点，搜索到就直接结束。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
struct edge{
int to,w;
};
vector<edge> G[110];
int f[110][110],n,q;
bool vis[110];
void dfs(int pos,int cnt){
if(G[pos].size()==1) return;
int ch[2],w[2],len=0;
for(auto i:G[pos]){//计算左右子节点以及权值
if(!vis[i.to]){
w[len]=i.w;
ch[len++]=i.to;
}
}
vis[pos]=1;
dfs(ch[0],cnt-1);
dfs(ch[1],cnt-1);
for(int i=1;i<=cnt;i++){
f[pos][i]=max(f[ch[1]][i-1]+w[1],f[ch[0]][i-1]+w[0]);
for(int j=0;j<=i-2;j++){
f[pos][i]=max(f[pos][i],f[ch[0]][j]+w[0]+f[ch[1]][i-j-2]+w[1]);
}
}
vis[pos]=0;
}
int main(){
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v;
edge e;
cin>>u>>v>>e.w;
e.to=v,G[u].push_back(e);
e.to=u,G[v].push_back(e);
}
dfs(1,q);
cout<<f[1][q];
return 0;
}