1074 二叉苹果树（树形dp）

心已赠人 2022-09-14 00:14 76阅读 0赞

**1. 问题描述：**

有一棵二叉苹果树，如果树枝有分叉，一定是分两叉，即没有只有一个儿子的节点。这棵树共 N 个节点，编号为 1 至 N，树根编号一定为 1。我们用一根树枝两端连接的节点编号描述一根树枝的位置。一棵苹果树的树枝太多了，需要剪枝。但是一些树枝上长有苹果，给定需要保留的树枝数量，求最多能留住多少苹果。这里的保留是指最终与1号点连通。

**输入格式**

第一行包含两个整数 N 和 Q，分别表示树的节点数以及要保留的树枝数量。接下来 N−1 行描述树枝信息，每行三个整数，前两个是它连接的节点的编号，第三个数是这根树枝上苹果数量。

**输出格式**

输出仅一行，表示最多能留住的苹果的数量。

**数据范围**

1 ≤ Q < N ≤ 100.  
N≠1,  
每根树枝上苹果不超过 30000 个。

**输入样例：**

5 2  
1 3 1  
1 4 10  
2 3 20  
3 5 20

**输出样例：**

21  
来源：[https://www.acwing.com/problem/content/description/1076/][https_www.acwing.com_problem_content_description_1076]

**2. 思路分析：**

分析题目可以知道选择子节点的时候是一定需要选择父节点的，所以在选择节点的时候是有依赖关系的，因为我们需要求解出最多能够保留苹果的数量，所以属于最优化问题，我们可以看成是**有依赖背包问题**的简化版本：将保留的边的数目看成是背包的容量（最多可以保留Q条边），边的权重看成是价值，每条边看成是体积为1，我们需要求解出在不超过背包容量Q的情况下能够获得的最大价值，使用有依赖的背包问题的求解思路即可。有依赖的背包问题其实是分组背包问题与树形dp的结合，首先我们需要声明一个二维数组dp，其中dp\[u\]\[j\]表示以u为根节点选j条边能够获得的最大价值；怎么样进行状态计算呢？我们可以在递归调用完当前节点u的子节点next\[0\]时候（回溯）更新当前父节点的信息（更新以当前的父节点所有背包容量的最大价值），可以使用两层循环枚举，第一层循环枚举背包容量i，第二层循环枚举背包容量为i的情况下对应的子节点next\[0\]占用的体积j，我们可以将当前节点u的每棵子树看成是一组物品，类似于分组背包问题中每一组的的物品，这里在枚举子树的时候不是枚举当前子树中的所有物品选还是不选，而是枚举子树占用的体积，这样比较容易操作而且时间复杂度不会太高，最终一定是可以枚举到与1联通的保留Q条分支的最大价值的。注意因为最终需要保留与1联通，所以dp\[u\]\[j\]以u为父节点的时候是一定选择了某条与子节点的边，这样才可以保证最终选择的边与1是联通的。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16][]

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        V = 0
        # fa表示节点u的父节点当为了避免两个点存在双向的联系导致死循环的问题
        def dfs(self, u: int, fa: int, dp: List[List[int]], g: List[List[tuple]]):
            for next in g[u]:
                # 我们只能够往下递归所以当next = fa表示直接跳过即可
                if next[0] == fa: continue
                self.dfs(next[0], u, dp, g)
                # 因为我们需要由子节点的信息更新到父节点所以递归回溯到这里的时候更新父节点的信息
                # 分组背包问题
                # 逆序枚举背包容量
                for i in range(self.V, 0, -1):
                    for j in range(i):
                        # 枚举所有以当前u为根节点背包容量为i的前提下子节点占用体积为j的最大价值
                        # 因为每一次枚举的时候都是枚举所有的背包容量所以最终一定会更新到最大值
                        # 因为当前的节点u需要占一个体积所以是dp[u][i - j - 1]
                        dp[u][i] = max(dp[u][i], dp[u][i - j - 1] + dp[next[0]][j] + next[1])
    
        def process(self):
            n, m = map(int, input().split())
            self.V = m
            g = [list() for i in range(n + 1)]
            for i in range(n - 1):
                a, b, c = map(int, input().split())
                # 无向图所以需要建两条边, 使用元组来封装边的终点以及权重
                g[a].append((b, c))
                g[b].append((a, c))
            dp = [[0] * (m + 1) for i in range(n + 1)]
            self.dfs(1, -1, dp, g)
            # 当前以1为根节点体积为m的能够获得的最大价值
            return dp[1][m]
    
    
    if __name__ == '__main__':
        print(Solution().process())

[https_www.acwing.com_problem_content_description_1076]: https://www.acwing.com/problem/content/description/1076/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/c1c2267bc4764b83b41f5549fe971e18.png