https://www.luogu.com.cn/problem/P2015
#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int M = 205;
struct edge {
int nxt, to, w;
}edges[M];
int idx;
int head[N];
int branch[N]; //记录每个节点的树的树枝数量
int f[N][M]; //f[i][j]是以i为根节点,有j条树枝的树的最优值
int n, q;
inline void add(int a, int b, int w)
{
edges[++idx].to = b;
edges[idx].nxt = head[a];
edges[idx].w = w;
head[a] = idx;
}
/*
@param root ...
@param fa ...
*/
void dfs(int root, int fa)
{
for (int e = head[root]; e != 0; e = edges[e].nxt) {
int to = edges[e].to;
if (to == fa) {
//避免递归到父节点
continue;
}
dfs(to, root);
branch[root] += branch[to] + 1; //父节点的树枝数等于子树的加一
/*
转化成一个分组背包问题
*/
for (int w = min(branch[root], q); w >= 1; --w) {
for (int i = min(branch[to], w - 1); i >= 0; --i) {
f[root][w] = max(f[root][w], f[root][w - i - 1] + f[to][i] + edges[e].w);
}
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("D:/VS CODE/C++/in.txt", "r", stdin);
freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
cin >> n >> q;
for (int i = 0; i < n - 1; ++i) {
int a, b, w;
scanf("%d %d %d", &a, &b, &w);
add(a, b, w);
add(b, a, w);
}
dfs(1, -1);
cout << f[1][q];
fclose(stdin);
fclose(stdout);
return 0;
}