洛谷-P2015 二叉苹果树

二叉苹果树

树形dp

设计状态：\(dp[u][i]\)，表示以结点 \(u\) 为根的子树，保留 \(i\) 条边的最大苹果数

状态转移：遍历每一个子节点 \(v\)

• 保留和 \(v\) 相连的边：\(dp[u][i] = dp[u][i - j - 1] + dp[v][j] + w_{uv}\)

\(j\) 为遍历 \([0, Q - 1]\) 表示以 \(v\) 为根的子树中保留了 \(j\) 条边，显然 \(j\) 不能等于 \(Q\)，因为还有一条边是 \(u\) 到 \(v\)

\(i\) 为当前子树总共保留 \(i\) 条边，遍历 \([0, Q]\)

\(w_{uv}\) 表示 \(u\) 和 \(v\) 相连的边上有多少个苹果

• 不保留和 \(v\) 相连的边：\(dp[u][i] = dp[u][i]\)

综上，状态转移为：\(dp[u][i] = max(dp[u][i], dp[u][i - j - 1] + dp[v][j] + w_{uv})\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
const ll maxn = 110;
const ll inf = 1e17 + 10;
vector<vector<array<int, 2>>>gra;
int n, q;
int dp[maxn][maxn];

void dps(int now, int pre)
{
    for(auto [nex, val] : gra[now])
    {
        if(nex == pre) continue;
        dps(nex, now);
        for(int i=q; i>=1; i--)
            for(int j=0; j<i; j++)
                dp[now][i] = max(dp[now][i], dp[now][i - j - 1] + dp[nex][j] + val);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    gra.resize(n + 1);
    for(int i=1; i<n; i++)
    {
        int a, b, k;
        cin >> a >> b >> k;
        gra[a].push_back({b, k});
        gra[b].push_back({a, k});
    }
    dps(1, 1);
    cout << dp[1][q] << endl;
    return 0;
}