$\LARGE\color{orange}{刷题日记(算法提高课)}$

这道题其实是 AcWing 10. 有依赖的背包问题 的一个变式

有依赖的背包问题里面，权值在节点上，本题权值在边上

我们可以仿照递归节点的方式来考虑本题，我们将节点的入边上的权值设为该点的权值，并且我们设每个点的体积均为 1

按照这种定义，只有根节点是没有权值的，不过这个并不影响，因为当我们遍历到某个节点而言，我们需要遍历这个节点的出边，并不会关注这个节点本身

也就是说，在递归某个节点时，该节点本身的权值是不用考虑的

在我们循环 $son$ 的体积时，由于不需要考虑 $u$ 的情况，因此其体积至多为 $j-1$ （减去 $u$ 的体积）

由于不需要考虑节点 $u$ ，因此也就不用为节点 $u$ 预留空间了

完整代码：

#include <iostream>
#include <cstring>

using namespace std;
const int N = 110, M = 2 * N, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];
int n, m;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

int dfs(int u, int father)
{
    for(int i = h[u]; i != -1; i = ne[i])
    {
        int son = e[i];
        if(son == father) continue;
        dfs(son, u);
        for(int j = m; j >= 0; j--)
            for(int k = 0; k <= j - 1; k++)//k循环的是边（也是体积），由于我们递归的对象是节点，因此边数只能到节点数减一
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[son][k] + w[i]);
    }
}

int main()
{
    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1; 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;
    return 0;
}