285 没有上司的舞会（树形dp）

我不是女神ヾ 2022-09-11 08:17 125阅读 0赞

**1. 问题描述：**

Ural大学有 N 名职员，编号为 1∼N。他们的关系就像一棵以校长为根的树，父节点就是子节点的直接上司。每个职员有一个快乐指数，用整数 Hi 给出，其中 1 ≤ i ≤ N。现在要召开一场周年庆宴会，不过，没有职员愿意和直接上司一起参会。在满足这个条件的前提下，主办方希望邀请一部分职员参会，使得所有参会职员的快乐指数总和最大，求这个最大值。

**输入格式**

第一行一个整数 N。接下来 N 行，第 i 行表示 i 号职员的快乐指数 Hi。接下来 N−1 行，每行输入一对整数 L，K，表示 K 是 L 的直接上司。

**输出格式**

输出最大的快乐指数。

**数据范围**

1 ≤ N ≤ 6000，  
−128 ≤ Hi ≤ 127

**输入样例：**

7  
1  
1  
1  
1  
1  
1  
1  
1 3  
2 3  
6 4  
7 4  
4 5  
3 5

**输出样例：**

5  
来源：[https://www.acwing.com/problem/content/description/287/][https_www.acwing.com_problem_content_description_287]

**2. 思路分析：**

分析题目可以知道职员之间的关系构成了一棵树，我们在树中不能选择相邻的两个节点，我们需要在所有可以选择的方案中求解出能够获得的最大快乐指数，根据这个特点可以知道这道题目的本质是**树形dp**，在树中使用dp的思想求解最优的方案，对于树形dp的题目我们只需要考虑某个根节点与子节点的关系推导出状态转移方程即可（也即只需考虑局部），只需要考虑局部的原因是我们可以使用dfs遍历树中的每一个节点，对于每一个节点（局部）都执行相同的操作，在dfs的过程求解出每一个点的所有选择方案能够获得的最大值，直到更新到根节点为止，因为树中的每一个节点都可以选或者不选，所以我们可以定义一个二维数组dp方便后面的状态计算，其中dp\[u\]\[0\]表示不选当前根节点u能够获得的最大快乐指数，dp\[u\]\[1\]表示选当前根节点u能够获得的最大快乐指数：可以发现当递归返回到当前这一层的时候（回溯）就需要更新一下当前根节点选或者不选对应的当前子树的最大快乐指数，对于当前根节点的每一个子树都是这样操作，这样到根节点的时候就求解出了选或者不选根节点能够获得的最大快乐指数，对于根节点的两种情况取一个max即可。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_18_color_FFFFFF_t_70_g_se_x_16][]

这里在建图的时候其实是有一个巧妙的方法，需要使用到三个数组分为为e，ne，h，下面是一个简单地建图的例子可以帮助理解其中的过程：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16][]

输入边的顺序为：2->4，1->2，1->5，1->3

① e\[1\] = 4，ne\[1\] = -1，h\[2\] = 1，idx = 2

② e\[2\] = 2，ne\[2\] = -1，h\[1\] = 2，idx = 3

③ e\[3\] = 3，ne\[3\] = 2，h\[1\] = 3，idx = 4

④ e\[4\] = 5，ne\[4\] = 3，h\[1\] = 4，idx = 5

因为使用的是python语言所以而python语言默认在1000左右，对于这道题目调用次数大于了1000所以需要设置一下最大的调用次数否则会出现运行时异常的错误，可以使用sys.setrecursionlimit(t)设置最大调用次数t。

**3. 代码如下：**

**python：**

下面的第一个代码写起来比较复杂，主要是创建有向图的过程，在创建有向图的时候使用一个非常巧妙的方法，使用到了e，ne，h三个数组来链接节点与节点之间的关系，其中e用来存储当前这一条边指向的顶点编号，例如e\[2\] = 3，表示当前按顺序输入的第二条边的指向的节点编号为3，ne用来存储当前边指向的节点编号对应的具有相同父节点编号的按顺序输入的上一条边的编号，例如3有三个孩子分别为\[4，5，6\]，并且这三条边是按顺序输入的，当遍历完3->6这条边之后执行i = ne\[t\]，此时i为上一条3指向的节点编号5对应的节点编号（3->5），h用来存储所有由当前的顶点出发的最后的那条边对应的节点编号；

from typing import List
    import sys
    # 因为python3最大的调用次数在1000左右如果不设置那么有的数据会爆栈
    sys.setrecursionlimit(6000)
    
    
    class Solution:
        idx = None
    
        # 处理输入输出数据
        def process(self):
            # 初始化idx用来唯一标识每一条边的位置
            self.idx = 1
            n = int(input())
            # w用来存储快乐指数, 一开始的时候先存储数字0这样后面的数字下标从1开始
            w = [0]
            # 注意是二维的dp列表, dp[i][0]表示不选当前的跟节点能够获得的最大快乐指数, dp[i][1]...选...获得的最大快乐指数
            dp = [[0] * 2 for i in range(n + 1)]
            # 列表e用来存储边的编号对应的节点编号, ne表示相同的父节点的前提下当前节点编号的上一条边的编号, h为当前编号对应的最后那条边的位置, 这三个数字用来连接图中节点与节点之间的关系
            e, ne, h = [0] * (n + 1), [0] * (n + 1), [-1] * (n + 1)
            # 输入快乐指数
            for i in range(n):
                w.append(int(input()))
            sta = [0] * (n + 1)
            # n - 1条边所以属于一颗树
            for i in range(n - 1):
                a, b = map(int, input().split())
                # 注意b是a的父节点
                self.add(e, ne, h, b, a)
                sta[a] = 1
            root = 1
            while sta[root] != 0: root += 1
            self.dfs(e, ne, h, w, dp, root)
            # 对于根节点的两种情况取一个max
            return max(dp[root][0], dp[root][1])
    
        # u为当前的根节点
        def dfs(self, e: List[int], ne: List[int], h: List[int], w: List[int], dp: List[List[int]], u: int):
            dp[u][1] = w[u]
            i = h[u]
            while i != -1:
                j = e[i]
                self.dfs(e, ne, h, w, dp, j)
                # 相同的父节点的上一条边的编号
                i = ne[i]
                dp[u][0] += max(dp[j][0], dp[j][1])
                dp[u][1] += dp[j][0]
    
        def add(self, e: List[int], ne: List[int], h: List[int], a: int, b: int):
            e[self.idx] = b
            ne[self.idx] = h[a]
            h[a] = self.idx
            # 更新全局变量idx
            self.idx += 1
    
    
    if __name__ == '__main__':
        print(Solution().process())

python创建有向图的第二种方式：每一个位置上的元素都是一个列表这样可以很方便地链接节点与节点之间的关系，g = \[list() for i in range(n)\]：

import sys
    # 设置递归最大调用次数
    from typing import List
    
    sys.setrecursionlimit(6010)
    
    
    def dfs(g: List[List[int]], dp: List[List[int]], w: List[int], u: int):
        dp[u][1] = w[u]
        # 遍历当前节点的所有顶点
        for x in g[u]:
            dfs(g, dp, w, x)
            # 递归返回到当前这一层的时候说明当前节点的某一个子树已经递归完成这个时候需要更新一下当前跟节点能够获得的最大快乐指数
            dp[u][0] += max(dp[x][0], dp[x][1])
            dp[u][1] += dp[x][0]
    
    
    if __name__ == '__main__':
        n = int(input())
        w = [0]
        for i in range(n):
            w.append(int(input()))
        # 声明有向图, 每一个位置都是一个list列表
        g = [list() for i in range(n + 1)]
        # 用来标记不是根节点的节点编号
        sta = [0] * (n + 1)
        for i in range(n - 1):
            # b是a的父节点
            a, b = map(int, input().split())
            g[b].append(a)
            sta[a] = 1
        dp = [[0] * 2 for i in range(n + 1)]
        root = 1
        # 找到当前树中的根节点
        while sta[root] != 0: root += 1
        dfs(g, dp, w, root)
        # 输出根节点是选还是不选能够获得的最大值
        print(max(dp[root][0], dp[root][1]))

[https_www.acwing.com_problem_content_description_287]: https://www.acwing.com/problem/content/description/287/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/99acb379901c4ca6b7311f00f7babd90.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAeXV6aGFuZ196eQ_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/926184abed0f4304a1be7aa53cc5252d.png