最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

给定一棵含有 $n$ 个结点的树，树根编号为 $1$，且树上的每条边有一个边权 $w_{edge_j}$

要求我们只保留树中的 $m$ 条边，使得 树根 所在的 连通块 的所有边 边权之和 最大

分析

想复习一下 背包DP 的同学，可以看看我之前写过的这篇 背包DP合集
这篇题解对于重复部分的知识不会再额外讲了QwQ

这题的题面其实就是 有依赖的背包 模型，不同的是把 物品价值 分给了 边 而不是 点

不过，对于一棵树来说，任意节点的入边（连向父节点的边） 都是 唯一 的

所以 边权 和 点权 在确定树的 根节点 以后，是可以视作一个东西的（入边价值 视作 该点价值）

常用的 有依赖的背包DP 集合划分方案有两个：

1. 子物品体积集合划分 $O(N \times V \times V)$ AcWing 10. 有依赖的背包问题【有依赖背包DP+子物品体积集合划分】
2. 分组背包集合划分 $O(N \times 2^k \times V)$ AcWing 487. 金明的预算方案【有依赖背包DP+分组背包集合划分】

对于本题来说，分组背包集合划分 会超时，因此采用 体积集合划分方案

闫氏DP分析法

状态表示—集合 $f_{i,j}$: 以 $i$ 为根节点的子树，包含 $i$ 的连通块的边数不超过 $j$ 的方案
状态表示—属性 $f_{i,j}$: 方案的边权之和最大 $Max$
状态计算—$f_{i,j}$
$$ f_{i,j} = \max\Big\{{ f_{i,j-1-k} + f_{son_i,k} + w_{edge_i} }\Big\} \quad k\in[0,j-1] $$

【注】这里 $k$ 最大枚举到 $j-1$ 是因为如果计算 该节点 对 父节点 的 贡献，必须保留他到 父节点 的 入边

Code

时间复杂度： $O(N \times V \times V)$

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110, M = N << 1;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
void dfs(int u, int father)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int ver = e[i];
        if (ver == father) continue;
        dfs(ver, u);
        for (int j = m; j >= 0; j -- )
            for (int k = 0; k <= j - 1; k ++ )  //枚举体积预留一条连向父节点的边
                f[u][j] = max(f[u][j], f[u][j - k - 1] + f[ver][k] + w[i]);
    }
}
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\n", f[1][m]);
    return 0;
}