<—点个赞吧QwQ

宣传一下算法提高课整理

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。

这棵树共 $N$ 个节点，编号为 $1$ 至 $N$，树根编号一定为 $1$。

我们用一根树枝两端连接的节点编号描述一根树枝的位置。

一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。

这里的保留是指最终与1号点连通。

输入格式

第一行包含两个整数 $N$ 和 $Q$，分别表示树的节点数以及要保留的树枝数量。

接下来 $N-1$ 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

输出格式

输出仅一行，表示最多能留住的苹果的数量。

数据范围

$1 \le Q \lt N \le 100$.
$N \neq 1$,
每根树枝上苹果不超过 $30000$ 个。

输入样例：

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

输出样例：

21

思路

闫氏$\text{DP}$分析法：
状态表示：$f_{i,j}$

• 以$i$为根节点的子树，包含$i$的连通块的边数不超过$j$的所有方案
• 属性：$\max$

状态计算：

• 这里$k$是枚举保留的边数
• 这里要减$1$的原因是要包含节点$i$
• 所以状态转移方程是$f_{i,j}=\max\lbrace f_{i,j−1−k}+f_{son_i,k}+w_{edge_i}\rbrace \quad k\in [0,j−1]$

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110,M = 2 * N;
int n,q;
int h[N],e[M],ne[M],w[M],idx;
int s[N];
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 fa) {
    for (int i = h[u];~i;i = ne[i]) {
        int v = e[i];
        if (v == fa) continue;
        dfs (v,u);
        s[u] += s[v];
        for (int j = min (s[u],q);j >= 1;j--) {
            for (int k = min (s[v],j - 1);k >= 0;k--) f[u][j] = max (f[u][j],f[u][j - k - 1] + f[v][k] + w[i]);
        }
    }
}
int main () {
    memset (h,-1,sizeof (h));
    cin >> n >> q;
    for (int i = 1;i <= n;i++) s[i] = 1;
    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][q] << endl;
    return 0;
}