AcWing 285. 没有上司的舞会
原题链接
简单
作者:
Scat
,
2024-04-11 20:04:38
,
所有人可见
,
阅读 1
树形dp
N = int(input())
mmap = [[] for i in range(N + 1)]
happies = [0]
f = [[0 for i in range(2)] for i in range(N + 1)]
for i in range(N):
happies.append(int(input()))
st = [False for i in range(N + 1)]
for i in range(N - 1):
a, b = map(int, input().split())
mmap[b].append(a)
st[a] = True
root = -1
for i in range(1, N + 1):
if not st[i]:
root = i
break
import sys
sys.setrecursionlimit(10000)
def dfs(u):
f[u][1] = happies[u]
for x in mmap[u]:
#经典,实在是太经典了,直接dfs
dfs(x)
f[u][1] += f[x][0]
f[u][0] += max(f[x][0], f[x][1])
dfs(root)
print(max(f[root][1], f[root][0]))