AcWing 285. 没有上司的舞会(Python)
原题链接
简单
作者:
习学学
,
2021-01-20 22:41:27
,
所有人可见
,
阅读 406
import sys
sys.setrecursionlimit(1000000)
n = int(input())
happy = [0] * (n+1)
h, e, ne = [-1] * (n+1), [0] * (2*n+1), [0] * (2*n+1)
idx = 0
is_root = [True] * (n+1) # 判断是否为根节点
dp = [[0] * 2 for _ in range(n+1)]
def add(a, b):
global idx
e[idx] = b
h[a], ne[idx] = idx, h[a]
idx += 1
def dfs(x):
dp[x][1] = happy[x]
i = h[x]
while i != -1:
child = e[i]
dfs(child)
dp[x][1] += dp[child][0]
dp[x][0] += max(dp[child][1], dp[child][0])
i = ne[i]
for i in range(1, n+1):
happy[i] = int(input())
for _ in range(n-1):
b, a = map(int, input().split())
add(a, b)
is_root[b] = False
for i in range(1, n+1):
if is_root[i]:
dfs(i)
print(max(dp[i][0], dp[i][1]))
break