派对的最大快乐值

[编程题]派对的最大快乐值

热度指数：4050 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

整个公司的人员结构可以看作是一棵标准的多叉树。树的头节点是公司唯一的老板，除老板外，每个员工都有唯一的直接上级，叶节点是没有任何下属的基层员工，除基层员工外，每个员工都有一个或多个直接下级，另外每个员工都有一个快乐值。

这个公司现在要办 party，你可以决定哪些员工来，哪些员工不来。但是要遵循如下的原则：

1.如果某个员工来了，那么这个员工的所有直接下级都不能来。

2.派对的整体快乐值是所有到场员工快乐值的累加。

3.你的目标是让派对的整体快乐值尽量大。

给定一棵多叉树，请输出派对的最大快乐值。

输入描述:

第一行两个整数 n 和 root，n 表示公司的总人数，root 表示公司的老板。

第二行 n 个整数 happy_i 表示员工 i 的快乐值。

接下来 n - 1 行每行两个整数 u_i 和 v_i 表示 u_i 是 v_i 的直接上级。

输出描述:

输出一个整数表示最大快乐值。

示例1

输入

输出

备注:


输入保证是一棵树

算法知识视频讲解

Python3

开始摆烂没意义

import sys
data = []
for line in sys.stdin:
    data.append(line.split())  # 每一行的输入
n = 0 # 公司总人数
happyValue = {}
tree = {}  # 存储每个员工的直接上下级关系
root = 0  # 根节点，老板的编号
for i, value in enumerate(data):
    if i == 0:
        n = int(value[0])
        root = int(value[1])
    elif i == 1:
        for j, happy in enumerate(value):
            happyValue[j+1] = int(happy)
    else:
            if int(value[0]) not in tree:
                tree[int(value[0])] = [int(value[1])]
            else:
                tree[int(value[0])].append(int(value[1]))    
def process(root):  # 从根节点开始，输出以root为上级的最大快乐值，root来的时候最大快乐值以及root不来的时候的最大快乐值
    if root not in tree:  # basecase:当前节点没有下级
      return [happyValue[root], 0]  # 来的时候为自己的快乐值，不来为0
    includeRoot, excludeRoot = happyValue[root], 0  # 包含根节点和不包含根节点的快乐值
    for value in tree[root]:
        data = process(value)  # 子树根节点来和不来的最大快乐值
        # 包含根节点，则子树根节点不能来
        includeRoot += data[1]
        # 不包含根节点，子树根节点可以来，可以不来
        excludeRoot += max(data[0], data[1])
    return [includeRoot, excludeRoot]
data = process(root)
print(max(data[0], data[1]))

发表于 2023-01-14 21:06:51 回复(0)