AcWing 285. 没有上司的舞会(Python list邻接表)
原题链接
简单
作者:
qiao
,
2023-01-25 15:28:42
,
所有人可见
,
阅读 147
Python 代码
import sys
sys.setrecursionlimit(1000000)
#防止递归次数越界
N = 6010
hy = [0] * N
has_fa = [False] * N
f = [[0] * N for _ in range(N)]
h = [[] for _ in range(N)]
def dfs(u):
f[u][1] = hy[u]
for j in h[u]:
dfs(j)
f[u][0] += max(f[j][0], f[j][1])
f[u][1] += f[j][0]
n = int(input())
for i in range(1,n+1):
hy[i] = int(input())
for _ in range(n - 1):
a, b = map(int, input().split())
h[b].append(a)
has_fa[a] = True
root = 1
while has_fa[root]:
root += 1
dfs(root)
print(max(f[root]))