【树形dp】洛谷P2015 二叉苹果树

Loading - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：

给你一个有边权的二叉树，要保留一定数量的边数，问到根节点的最大权值和是多少

思路：

这是一道树形dp题

不论是线性dp，还是树形dp，我们都先设计状态

设计状态时考虑结点的属性和题目给的决策

一个结点的属性就是在树上的位置和最大的权值和

题目给的决策有两个：

1.选取该边并获得该边的边权

2.不选该边

这道题我们要求最大的权值和，而且有限制：要保留一定数量的边数，因此可以想到这是一个背包问题，因为在01背包问题中，我们要获取最大的利益和，并且背包有体积限制，因此不难想到这是个树上背包问题

我们设状态为，表示在结点保留条边

因此转移方程就是

Code:

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e2+10;
int n,m,cnt=0;
int head[mxn],f[mxn][mxn],sz[mxn];
struct ty{
    int to,next,w;
}edge[mxn<<1];
void add(int u,int v,int w){
    edge[cnt].w=w;
    edge[cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
void dfs(int x){
    for(int i=head[x];~i;i=edge[i].next){
        int v=edge[i].to;
        dfs(v);
        sz[x]+=sz[v]+1;
        for(int j=min(sz[x],m);j>=0;j--){
            for(int k=min(j-1,sz[v]);k>=0;k--){
                f[x][j]=max(f[x][j],f[x][j-k-1]+f[v][k]+edge[i].w);
            }
        }
    }
}
int main(){
    int x,y,v;
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n-1;i++){
        scanf("%d%d%d",&x,&y,&v);
        add(x,y,v);
    }
    dfs(1);
    printf("%d\n",f[1][m]);
    return 0;
}

关于dfs：

我们维护一个sz数组，用来保存该结点的下面有多少条边，然后就是在枚举该结点保留多少条边，并且这个要倒着枚举，因为这是01背包，对应于01背包中倒着枚举背包容量

然后就是在枚举怎么把要保留的边分配给左右两个结点

维护完所有的数组后就是我们所要求的答案了