洛谷P2015 二叉苹果树 题解

题目链接：P2015 二叉苹果树

题意：

有一棵苹果树，如果树枝有分叉，一定是分二叉（就是说没有只有一个儿子的结点）

这棵树共有 N N N 个结点（叶子点或者树枝分叉点），编号为 1 ∼ N 1 sim N 1∼N，树根编号一定是 1 1 1。

我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有 4 4 4 个树枝的树：

2   5
  / 
  3   4
    /
    1

现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

给定需要保留的树枝数量 m m m ，求出最多能留住多少苹果。

经典的树形依赖背包（树上背包）

设 d p [ u ] [ j ] dp[u][j] dp[u][j] 表示 u u u 结点所在子树保留 j j j 条边所能得到的最大苹果树

则有
d p [ u ] [ j ] = max ⁡ ( d p [ u ] [ j ] , d p [ u ] [ j − k − 1 ] + d p [ v ] [ k ] + w ( u , v ) ) dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w(u,v)) dp[u][j]=max(dp[u][j],dp[u][j−k−1]+dp[v][k]+w(u,v))
为什么是 j − k − 1 j-k-1 j−k−1 呢

因为 k k k 是 v v v 所在子树的分配边数，但是你要花一条边去连上 v v v

不然你给了 v v v 一共 k k k 条边最后没连上它啥也没有

时间复杂度 O ( n m ) O(nm) O(nm)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)

struct Edge
{
    int u,v,w,next;
}e[N<<1];
int pos=1,head[N];
void addEdge(int u,int v,int w)
{
    e[++pos]={u,v,w,head[u]};
    head[u]=pos;
}
int n,m,sz[N],dp[N][N];
void dfs(int u,int f)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        dfs(v,u);
        sz[u]+=sz[v]+1;
        for(int j=min(sz[u],m); j>=1; j--)
            // for(int k=min(sz[v],j-1); k>=0; k--)
            for(int k=0; k<=min(sz[v],j-1); k++) //这里正反都不影响
                dp[u][j]=max(dp[u][j],dp[u][j-k-1]+dp[v][k]+e[i].w);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v,w; i
        cin >> u >> v >> w;
        addEdge(u,v,w);addEdge(v,u,w);
    }
    dfs(1,1);
    cout << dp[1][m] << endl;
    return 0;
}

转载请说明出处