代码源树上背包板子

野性酷女 2024-03-16 20:35 72阅读 0赞

树上背包1

[树上背包1 - 题目 - Daimayuan Online Judge][1 - _ - Daimayuan Online Judge]

题意：

![2bfbc9f698234a268774071f64ffd369.png][]

![de18ddb37f3247dab94ed5b159e90645.png][]

思路：

在树上做背包

想象一棵子树，结点u有很多子树v

把这些子树v想象成一个个物品，假设我们已经枚举到了v这棵子树

因为u整棵树选的点数恰好为m，我们去枚举v这棵子树中选的点数，和前面遍历的这些多棵子树的选的点数，把结果存到tmp数组里，然后再用tmp数组给dp赋值

注意这里的sz数组，因为我们在遍历“物品”的时候，是不包含u这个结点的，因此sz一开始为0而不是1，等到所有物品遍历完之后，再算上u这个结点

算上u这个结点，一方面是sz\[u\]++，另一方面是更新dp数组

这样我们就做完背包了

这样乍看一眼复杂度是n^3的，但是事实上是n^2的，为什么呢

树上背包在合并时这么多个子树中点对之间只有1的贡献，每对点对只会在它们的lca处有贡献，所以是n^2的

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=2e3+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N,Q,Fa,u,m;
    int tot=0;
    int a[mxn],dp[mxn][mxn];
    int head[mxn],sz[mxn];
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        sz[u]=0;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            static int tmp[mxn];
            memset(tmp,-0x3f,sizeof(tmp));
            for(int j=0;j<=sz[u];j++){
                for(int k=0;k<=sz[edge[i].to];k++){
                    tmp[j+k]=max(tmp[j+k],dp[u][j]+dp[edge[i].to][k]);
                }
            }
            for(int j=0;j<=sz[u]+sz[edge[i].to];j++) dp[u][j]=tmp[j];
            sz[u]+=sz[edge[i].to];
        }
        sz[u]++;
        for(int i=N;i>=1;i--) dp[u][i]=dp[u][i-1]+a[u];
        dp[u][0]=0;
    }
    void solve(){
        cin>>N>>Q;
        G_init();
        for(int i=2;i<=N;i++){
            cin>>Fa;
            add(i,Fa);
            add(Fa,i);
        }
        for(int i=1;i<=N;i++) cin>>a[i];
        dfs(1,0);
        while(Q--){
            cin>>u>>m;
            cout<<dp[u][m]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

树上背包2

[树上背包2 - 题目 - Daimayuan Online Judge][2 - _ - Daimayuan Online Judge]

题意：

![48a5a86df53a498f9f2f8002ec86295a.png][]

![cccb582055ca4055b735063132435e20.png][]

思路：

和之前的一样，只不过背包大小需要加限制

值得注意的是复杂度，这个的复杂度是O(nm)的

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=5e4+10;
    const int mxe=5e4+10;
    const int mxm=1e2+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N,Q,Fa,u,m;
    int tot=0;
    int a[mxn],dp[mxn][mxm];
    int head[mxn],sz[mxn];
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        sz[u]=0;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
            static int tmp[mxn];
            for(int j=0;j<=min(sz[u]+sz[edge[i].to],100);j++) tmp[j]=-Inf;
            for(int j=0;j<=min(sz[u],100);j++){
                for(int k=0;k<=sz[edge[i].to]&&j+k<=100;k++){
                    tmp[j+k]=max(tmp[j+k],dp[u][j]+dp[edge[i].to][k]);
                }
            }
            for(int j=0;j<=min(sz[u]+sz[edge[i].to],100);j++) dp[u][j]=tmp[j];
            sz[u]+=sz[edge[i].to];
        }
        sz[u]++;
        for(int i=min(sz[u],100);i>=1;i--) dp[u][i]=dp[u][i-1]+a[u];
        dp[u][0]=0;
    }
    void solve(){
        cin>>N>>Q;
        G_init();
        for(int i=2;i<=N;i++){
            cin>>Fa;
            add(i,Fa);
            add(Fa,i);
        }
        for(int i=1;i<=N;i++) cin>>a[i];
        dfs(1,0);
        while(Q--){
            cin>>u>>m;
            cout<<dp[u][m]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

树上背包3

[树上背包3 - 题目 - Daimayuan Online Judge][3 - _ - Daimayuan Online Judge]

题意：

![d8123dddef39474f8cf039ac628674fa.png][]

![4f8ffd339543427f80443480ba2a23f9.png][] 思路：

这是标准的树上背包问题

每个子树都有选or不选两种决策

做法是在dfs序上做背包，如果不选，就是跳过这棵子树，选就从i+1的时间戳转移过来

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    using i64 = long long;
    
    const int mxn=2e3+10;
    const int mxe=2e3+10;
    const int mxm=1e4+10;
    const int mod=1e9+7;
    const int Inf=0x3f3f3f3f;
    
    int N,M,Fa;
    int tot=0,idx=0;
    int a[mxn],w[mxn],dp[mxn][mxm];
    int head[mxn],id[mxn],L[mxn],R[mxn];
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void dfs(int u,int fa){
        L[u]=++idx;
        id[idx]=u;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
        }
        R[u]=idx;
    }
    void solve(){
        cin>>N>>M;
        G_init();
        for(int i=2;i<=N;i++){
            cin>>Fa;
            add(i,Fa);
            add(Fa,i);
        }
        for(int i=1;i<=N;i++) cin>>a[i];
        for(int i=1;i<=N;i++) cin>>w[i];
        dfs(1,0);
        for(int j=1;j<=M;j++) dp[N+1][j]=-Inf;
        for(int i=N;i>=1;i--){
            for(int j=0;j<=M;j++){
                int u=id[i];
                dp[i][j]=dp[R[u]+1][j];
                if(j>=w[u]) dp[i][j]=max(dp[i][j],dp[i+1][j-w[u]]+a[u]);
            }
        }
        for(int j=0;j<=M;j++){
            if(dp[1][j]<0) cout<<0<<'\n';
            else cout<<dp[1][j]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[1 - _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/8/problem/269
[2bfbc9f698234a268774071f64ffd369.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/e201dc85e1654482bf5650dd1483b3f0.png
[de18ddb37f3247dab94ed5b159e90645.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/5cbb943e5bcf4aa09988b679755fc0d5.png
[2 - _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/8/problem/270
[48a5a86df53a498f9f2f8002ec86295a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/2c3591cb788b4b298bbac202506afc1f.png
[cccb582055ca4055b735063132435e20.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/530598b1f9ad4aa7836c06c8d5adf3ed.png
[3 - _ - Daimayuan Online Judge]: http://oj.daimayuan.top/course/8/problem/271
[d8123dddef39474f8cf039ac628674fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/ad1cdde13ab848b28d34bd4c6606f5f7.png
[4f8ffd339543427f80443480ba2a23f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/840641c2592840d9a9eb61cb6aa2da8c.png