题目大意

给出一个以 $1$ 号节点为根的 $n$ 个节点的二叉树，每条边上有一个权值，求最多选 $m$ 条边（与根节点连通）的最大权值和是多少。

输入样例：

5 2
1 3 1
1 4 10
2 3 20
3 5 20

输出样例：

21

• 树形DP
• 分组背包

做起来并没有用到二叉树的性质。

时间复杂度 $O(n^3)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

const int N = 110, M = N * 2;

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int n, m;
int f[N][N];        //  f[i][j]记录i号节点为根的子树中选择j条边的最大价值
int cnt[N];         //  cnt[i]记录以i号节点为根的子树共有多少条边

void dfs(int u, int fa)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs(j, u);
        cnt[u] += cnt[j] + 1;

        for(int k = cnt[u]; k; k --)
            for(int l = 0; l <= cnt[j] and l < k; l ++)
                f[u][k] = max(f[u][k], f[u][k - l - 1] + w[i] + f[j][l]);
    }
    //printf("%d:\n", u);
    //for(int i = 0; i <= cnt[u]; i ++)  printf("%d ", f[u][i]);  puts("");
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
        add(b, a, c);
    }

    dfs(1, -1);
    printf("%d", f[1][m]);
    return 0;
}