洛谷P2015 二叉苹果树 题解

题目链接：P2015 二叉苹果树

题意：

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

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

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

2   5
 \ / 
  3   4
   \ /
    1

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

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

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

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

则有

$$dp[u][j]=\max(dp[u][j],dp[u][j-k-1]+dp[v][k]+w(u,v))$$

为什么是 $j-k-1$ 呢

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

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

但是填表法会被卡到 $O(nm^2)$ ，所以考虑刷表法

时间复杂度 $O(nm)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
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],tmp[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);
        for(int j=0; j<=min(sz[u],m); j++)
            tmp[j]=dp[u][j];
        for(int j=0; j<=min(sz[u],m); j++)
            for(int k=0; k<=min(sz[v],m)&&j+k+1<=m; k++)
                dp[u][j+k+1]=max(dp[u][j+k+1],tmp[j]+dp[v][k]+e[i].w);
        sz[u]+=sz[v]+1;
        // 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<n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w);addEdge(v,u,w);
    }
    dfs(1,1);
    cout << dp[1][m] << endl;
    return 0;
}