一道经典的树形dp，其树形DP的原理是递归求解树状结构，并返回已经确立的状态值，形式多为记忆化搜索形式。而树形DP也常常跟其他DP联系起来，这道题就是将树形DP和背包DP联系起来的一道题。
而且该题是01背包，所以要注意(i,j)的枚举顺序。还要注意j和k的取值范围。
(Code)
#include <bits/stdc++.h>
#define N 101111
#define M 1011
using namespace std;
int n, m, ans, cnt, lin[N], dp[M][M], siz[M];//第一个表示节点的数，第二个表示要选的数。
struct cym {
int from, to, len, nex;
}e[N];
inline void add(int u, int v, int l)
{
e[++cnt].from = u;
e[cnt].len = l;
e[cnt].to = v;
e[cnt].nex = lin[u];
lin[u] = cnt;
}
inline void dfs(int now, int fa)
{
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to, w = e[i].len;
if (to == fa) continue;
dfs(to, now);
// siz[now] += siz[to] + 1;
for (int j = min(siz[now], m); j; j--)
for (int k = min(siz[to], j - 1); k >= 0; k--)
dp[now][j] = max(dp[now][j], dp[now][j - k - 1] + w + dp[to][k]);
}
}
inline void init(int now, int fa)
{
siz[now] = 1;
for (int i = lin[now]; i; i = e[i].nex)
{
if (e[i].to == fa) continue;
init(e[i].to, now);
siz[now] += siz[e[i].to];
}
return;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n - 1; i++)
{
int u, v, l;
scanf("%d%d%d", &u, &v, &l);
add(u, v, l);
add(v, u, l);
}
init(1, -1);
dfs(1, 0);//从顶层开始搜索，默认根节点的父亲是-1
ans = dp[1][m];
printf("%d", ans);
return 0;
}
/*
5 3
1 2 0
1 5 1
5 3 100
5 4 1
*/