蓝桥杯训练第二周

P2015 二叉苹果树 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

屮,一开始想当然的以为剪掉了其中一个边,其子树部分全部都会脱落,没想到剪掉一个边紧紧只是剪掉一个边,子树不会消失

很明显的,我们要考虑树形$dp$,因为剪掉哪条边是不确定的,那么暴力求的话,每条边都剪或不剪,时间复杂度为$O(2^n)$

如果我剪掉了这条边之后对后面的子树没有影响.所以具备无后效性,可以考虑树形$dp$或者是记忆化搜索

设方程 $dp[u][k]$ 为节点$u$保留$k$个节点的最大答案,那么明显的,我们设$u$此时保留了$i$个节点,其儿子$v$保留了$j$个节点,那么存在: $dp[u][i]=max(dp[u][i],dp[u][i-j-1]+dp[v][j]+w)$

为什么是$i-j-1$? 显然,我们从当前节点到儿子节点的这条边是不能删去的,不然的话没办法进行状态转移

接下来引入 - 背包

为什么是背包?我们直接把该题转化为:在当前节点$u$和其子树$v$的所有边中,选择几个边使得边权和最大,这不就是背包嘛?所以我们要倒序遍历

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, mod = 1e9 + 7;
signed main()
{
    std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, k; cin >> n >> k;
    vector<int> sz(n + 1);
    vector<pair<int, int>> g[n + 1];
    vector<vector<int>> dp(n + 1, vector<int>(n + 1));
    for (int i = 1; i <= n - 1; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back({b, c}), g[b].push_back({a, c});
    }
    function<void(int, int)> dfs;
    dfs = [&](int u, int fa) -> void
    {
        sz[u] = 1;
        for (auto now : g[u])
        {
            int x = now.first, w = now.second;
            if (x == fa)
                continue;
            dfs(x, u);
            sz[u] += sz[x];
            for (int i = min(sz[u], k); i; i--)
            {
                for (int j = min(sz[x], i - 1); j >= 0; j--)
                {
                    dp[u][i] = max(dp[u][i], dp[u][i - j - 1] + dp[x][j] + w);
                }
            }
        }
    };
    dfs(1, -1);
    cout << dp[1][k] << '\n';
    return 0;
}