1220. 生命之树
摘要
Title: 1220. 生命之树
Tag: 树形dp
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1220. 生命之树
-
题意
见原题
-
思路
树形dp，求树中连通块的最大权值
求最大值的函数在dfs函数结尾求，保证每个顶点都会被遍历到 -
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39'''
Author: NEFU AB-IN
Date: 2022-04-03 17:55:14
FilePath: \ACM\Acwing\1220.py
LastEditTime: 2022-04-03 19:09:18
'''
import sys
sys.setrecursionlimit(int(2e9))
N = int(1e5 + 10)
INF = int(1e18)
g = [[] for _ in range(N)]
dist = [0] * N
ans = -INF
def dfs(fa, u):
global ans
dist[u] = a[u]
for v in g[u]:
if v == fa:
continue
dfs(u, v)
dist[u] += max(0, dist[v])
ans = max(ans, dist[u])
n = int(input())
a = list(map(int, input().split()))
a = [0, *a]
for i in range(n - 1):
u, v = map(int, input().split())
g[u].append(v)
g[v].append(u)
dfs(-1, 1)
print(ans)