AcWing 1074 . 二叉苹果树

题目传送门

#include 

using namespace std;
const int N = 110;
const int M = N * 2;
int n;//表示树的节点数
int m;//表示要保留的树枝数量(背包容量)
int h[N], e[M], w[M], ne[M], idx;
int f[N][N];
//状态表示f[i,j]: 以i为根节点的子树，包含i的连通块的边数不超过j的方案
//状态计算f[i,j]: 方案的边权之和最大Max

//邻接表模板
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]) { //物品组
        if (e[i] == father)continue;    //不走回头路,节约使用变量j,人人有责
        dfs(e[i], u);           //预求父亲，先算儿子，孙子，重孙子...
        //分组背包
        for (int j = m; j; j--)         //体积
            for (int k = 0; k < j; k++) //决策，枚举体积预留一条连向父节点的边.
                /* 不能到j,因为占去了一条这是分组背包模型，表示选择当前这组物品中的“体积为k + 1，
                 价值为f[e[i]][k] +w[i]的物品”可以获得的最大价值。
                Q:为何是k+1不是k啊
                A:因为如果想保留当前子树中的某些树枝，就必须保留从父节点下来的这条树枝，
                 这里+1就是给父节点下来的这条树枝留出位置。
                */
                f[u][j] = max(f[u][j], f[u][j - 1 - k] + f[e[i]][k] + w[i]);
    }
}

int main() {
    //邻接表初始化
    memset(h, -1, sizeof h);
    cin >> n >> m;
    //读入n-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);
    }
    //根节点是1号点，开始利用dfs进行动态规划，树型dp
    dfs(1, -1);
    //输出
    printf("%d", f[1][m]);//以1号节点为根，边数不超过m（最大背包上限）的最大值
    return 0;
}