今天非常upset

用户名：dotcpp0744007

访问量：904

签　名：

等　　级
排　　名	13254
经　　验	936
参赛次数	0
文章发表	16
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

小白随便写的，记录一下
浏览：55

小白随便写的，记录一下，蓝桥杯练习，还有就是idle真难用
浏览：257

小白随便写的，记录一下，python开荒
浏览：74

你可能喜欢

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

小白随便写的，记录一下，python开荒

　　作者: 今天非常upset　　　　发表时间：2024-04-09 00:05:34 浏览：74　|　评论：0　

原题链接：没有上司的晚会

```python
"""
树形dp吧这题，这题很经典，但大多写法都是c/c++ 写了一下python
然后大部分思路都是dfs深搜
这里写了一下层次遍历的思路 其实和dfs的差不多 但还是提供一下思路
代码比较多 也比较难看懂 建议先去了解一下这题的大致思路再来看这篇题解
注释已经尽量详细了
"""
import sys
sys.setrecursionlimit(10000) # 设置一下递归深度 不然过不了

n = int(input()) # 接收n

fa = [0 for _ in range(n + 1)]  # 存储第i个节点的父节点

so = [[] for _ in range(n + 1)] # 存储第i个节点的子节点

val = [0] # 存储快乐度

boo = [True for _ in range(n + 1)] # 找根节点用

dep = [0 for _ in range(n + 1)]  # 存储每个节点的层次

def init_dep(node, h):
    # 递归初始化dep数组
    if so[node]:
        for i in so[node]:
            dep[i] = h + 1
            init_dep(i, dep[i])

for _ in range(n):
    val.append(int(input())) # 接收i的快乐度

for _ in range(n - 1):
    data = list(map(int, input().split()))  # 接收 L K
    fa[data[0]] = data[1]
    so[data[1]].append(data[0])
    boo[data[0]] = False

data_end = input().split() # 接收最后的0 0

root = 0 # 记录根节点
for i in range(1, n + 1):
    if boo[i] == True:
        root = i
        break

# 此时root 指向根节点
dep[root] = 1
init_dep(root, 1) # 完成dep数组初始

max_dep = max(dep)  # 记录最大层次
nodes = [[] for _ in range(max_dep + 1)] # 存储每层的节点下标
for i in range(1, n + 1):
    nodes[dep[i]].append(i)  # 初始化nodes数组

dp = [[0, 0] for _ in range(n + 1)]  # dp 数组 两个状态 选和不选

# 层次遍历 从最后一层开始 逐层往上 到第一层 即根节点
for i in range(max_dep, 0, -1):
    for node in nodes[i]: # 获得每层的节点下标
        dp[node][0] = 0 # 不选时默认为0
        dp[node][1] = val[node] # 选时默认为该点快乐度
        if so[node]: #  如果该点有孩子
            for son in so[node]:
                dp[node][0] += max(dp[son][0], dp[son][1])
                dp[node][1] += dp[son][0]
"""
上面是状态转移方程
对于每一个节点 dp[i][0]表示不选这个点
不选时其子节点可以选也可以不选 所以就取子节点取和不取两个情况的最大值累加
dp[i][1]表示选这个点
选时则累加子节点不选的值就行
"""

# 循环结束 根节点存储全局最优值
print(max(dp[root][0], dp[root][1]))

```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

今天非常upset

TA的其他文章

你可能喜欢

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

假币问题（C语言代码）

C语言训练-排序问题<1> （C语言代码）

小白随便写的，记录一下，python开荒

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【排队买票】（C语言代码）

WU-复数求和（C++代码）

剪刀石头布（C语言代码）

三角形（C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

格式化数据输出（C语言代码）

今天非常upset

TA的其他文章

你可能喜欢

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

假币问题 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

小白随便写的，记录一下，python开荒

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【排队买票】 （C语言代码）

WU-复数求和 （C++代码）

剪刀石头布 （C语言代码）

三角形 （C语言代码）

C语言程序设计教程（第三版）课后习题9.6 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

格式化数据输出 （C语言代码）

假币问题（C语言代码）

　　评论区

【排队买票】（C语言代码）

WU-复数求和（C++代码）

剪刀石头布（C语言代码）

三角形（C语言代码）

格式化数据输出（C语言代码）