二叉苹果树

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 977 字

根固定为1的二叉树，保留恰好Q条边，使保留边

一本通
例

正文

/*
原题：二叉苹果树（一本通 5.2 例1）
题意：根固定为 1 的二叉树，保留恰好 Q 条边，使保留边上的苹果总和最大。
思路：树形背包 dp[u][j] 表示 u 子树内选 j 条边的最大苹果；合并儿子时选其分支需占用连边 u-v。根答案为 dp[1][Q]。
复杂度：O(N*Q^2) 时间，O(N*Q) 空间。
易错点：边权在连边上，选儿子分支要算上 u-v 这条边；根不计入连父边。
*/
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int n,q;
vector<pair<int,int>> g[N];
int dp[N][N];
int sz[N];
void dfs(int u,int fa){
    sz[u]=0;
    for(int j=0;j<=q;j++)dp[u][j]=0;
    for(auto&e:g[u]){
        int v=e.first,w=e.second;
        if(v==fa)continue;
        dfs(v,u);
        sz[u]+=sz[v]+1;
        for(int j=min(q,sz[u]);j>=1;j--){
            for(int k=1;k<=sz[v]+1&&k<=j;k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k-1]+w);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        g[u].push_back({v,w});
        g[v].push_back({u,w});
    }
    dfs(1,0);
    cout<<dp[1][q]<<"\n";
    return 0;
}

二叉苹果树

正文

一本通·提高篇的其它内容