二叉苹果树

· · 个人记录

二叉苹果树

题目链接

凌晨0:31

分析

给你一棵树，只能保留 q 个树枝（边），最大的苹果数量

因为是在树上，又有容量（树枝个数）和最大价值，不难想到树上背包

树上背包

所以设 dp[i][j][k] 为 以 i 为根的子树中，前 j 个子树，选 k 个树枝，最大的苹果数

由背包问题的优化，可以换为滚动数组，将 j 一维压缩，再倒序遍历 j

那么从节点 u 一层一层地往下枚举，枚举每个子树根 v ，可得：

dp[i][j]=max\{dp[i][j-k-1]+dp[v][k]+w\{u,v\}\} (0 \leq j \leq q , 0 \leq k < j)

其中 j-k-1 是除 v 子树外树枝数

那么实现便是

::::info[DFS代码]{open}

void dfs(int x,int fa){//x：以x为根的子树  fa：当前节点的父亲（不重复） 
    for(auto i:g[x]){//遍历子树 
        if(i.first==fa){//遍历到父亲，就下一个（跳过） 
            continue; 
        }
        dfs(i.first,x);//统计子树信息 
        for(int j=q;j>=1;j--){//枚举容量（树枝数） 原为 dp[i][j][k] 以i为子树，前j个枝，选k个，苹果数最大，压维后需逆序 
            for(int k=0;k<j;k++){//枚举当前树枝容量 
                dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[i.first][k]+i.second);//更新，注意是j-k-1不是j-k，因为 x->i 连边也应加上 
            }
        }
    }
    return;
}

::::

时间复杂度 O(nq^2) ，对于这道题的 1 \leq Q < N \leq 100 来说已经足够了

优化

但还可以再优化一点

因为 j 是当前子树的树枝个数，但 j \leq q ，所以只用枚举到当前子树 min\{siz[i],q\} 即可，而同理，k 也只需枚举 k < min\{siz[v],j\}

跑一遍预处理 siz 数组

::::info[预处理]{open}

void solve(int x,int fa){
    for(auto i:g[x]){//遍历子树 
        if(i.first==fa){//遍历到父亲，就下一个（跳过） 
            continue; 
        }
        solve(i.first,x);//统计子树信息 
        siz[x]+=siz[i.first]+1;//树枝数=字数树枝数+1 
    }
    return;
}

:::: 再判断 j \leq min\{siz[i],q\} , k < min\{siz[v]+1,j\}

注意这里 siz[v] 要加1，因为是 < ，但是是可以选 siz[v] 个的

AC Code

::::warning[请勿copy]

//二叉苹果树
//树形dp 
#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
using namespace std;
int n,q;
vector<pair<int,int>>g[310];//链式前向星亦可 
int dp[110][110];//dp[i][j]表示在以i为根的子树中，留下j个树枝，最多能留住的苹果数量 
int siz[110];
void solve(int x,int fa){
    for(auto i:g[x]){//遍历子树 
        if(i.first==fa){//遍历到父亲，就下一个（跳过） 
            continue; 
        }
        solve(i.first,x);//统计子树信息 
        siz[x]+=siz[i.first]+1;//树枝数=字数树枝数+1 
    }
    return;
}
void dfs(int x,int fa){//x：以x为根的子树  fa：当前节点的父亲（不重复） 
    for(auto i:g[x]){//遍历子树 
        if(i.first==fa){//遍历到父亲，就下一个（跳过） 
            continue; 
        }
        dfs(i.first,x);//统计子树信息 
        for(int j=min(siz[x],q);j>=1;j--){//枚举容量（树枝数） 原为 dp[i][j][k] 以i为子树，前j个枝，选k个，苹果数最大，压维后需逆序 
            for(int k=0;k<min(siz[i.first]+1,j);k++){//枚举当前树枝容量 (<!) 
                dp[x][j]=max(dp[x][j],dp[x][j-k-1]+dp[i.first][k]+i.second);//更新，注意是j-k-1不是j-k，因为 x->i 连边也应加上 
            }
        }
    }
    return;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<n;i++){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});//存树（图） 
    }
    solve(1,0);
    dfs(1,0);//从1开始遍历 
    cout<<dp[1][q];//在1节点，留q个树枝，最多能留住的苹果数 
    return 0;
}

::::

总结

这是一道很模板的树上背包，但由于是树枝（边）上有价值，所以要细心改动一些，在细节上也要小心

很像选课这道题，但除了边上有价值以外，这道题一定是一棵二叉树！！！所以只有两条边，没有选课麻烦，但这个通解总能行

一般来说，树形dp都是先统计子树的答案，再汇总到根来计算，如 siz,sum 等数组的统计，约等于记忆化，但更多是dp，从叶子往上递推（一般）

几个经典模型：

树形dp题