树形DP分组背包入门 洛谷二叉苹果树

https://www.luogu.com.cn/problem/P2015

#include <bits/stdc++.h>
using namespace std;

const int N = 205;
const int M = 205;

struct edge {
    int nxt, to, w;
}edges[M];

int idx;        
int head[N];  
int branch[N];  //记录每个节点的树的树枝数量
int f[N][M];    //f[i][j]是以i为根节点，有j条树枝的树的最优值

int n, q;

inline void add(int a, int b, int w) 
{
    edges[++idx].to = b;
    edges[idx].nxt = head[a];
    edges[idx].w = w;
    head[a] = idx; 
}

/* 
    @param root ...
    @param fa   ...
 */
void dfs(int root, int fa)
{
    for (int e = head[root]; e != 0; e = edges[e].nxt) {
        int to = edges[e].to;
        if (to == fa) {
            //避免递归到父节点
            continue;
        }

        dfs(to, root);
        branch[root] += branch[to] + 1;  //父节点的树枝数等于子树的加一

        /*  
            转化成一个分组背包问题
         */
        for (int w = min(branch[root], q); w >= 1; --w) {
            for (int i = min(branch[to], w - 1); i >= 0; --i) {
                f[root][w] = max(f[root][w], f[root][w - i - 1] + f[to][i] + edges[e].w);
            }
        }
    }
}

int main() 
{
#ifndef ONLINE_JUDGE
    freopen("D:/VS CODE/C++/in.txt", "r", stdin);
    freopen("D:/VS CODE/C++/out.txt", "w", stdout);
#endif
    cin >> n >> q;

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

    dfs(1, -1);

    cout << f[1][q];


    fclose(stdin);
    fclose(stdout);
    return 0;
}