累积节点

环绕送货完了，但Zero的数据结构是树形的——需要累积节点。

"累积？"CC问。

"对。"你说，"给定一棵树，每个节点有一个值。选一个连通块，使得权值和最大。"

"连通块？"

"对。"你说，"节点之间通过边连接，选的要连在一起。"

"最大？"

"对。"你说，"用树形DP。"

"树形DP？"

"对。"你说，"$dp[u]$表示以$u$为根的子树中，选连通块的最大权值和。"

"转移？"

"对。"你说，"$dp[u]=a[u]+\sum\max(0,dp[v])$。"

"$\max(0,dp[v])$？"

"对。"你说，"如果子树的贡献是负的，就不选它。"

"第47个节点。"你说，"权值47——如果它的子树都是正的，全选。"

"如果有负的？"

"不选。"你说，"只选正的，累积起来。"

"像捡钱？"

"对。"你说，"像捡钱——地上的钱捡，坑里的不跳。"

"坑？"

"对。"你说，"负权值就是坑——跳进去，损失。"

"咋避？"

"不选。"你说，"$\max(0,\dots)$就是不跳坑。"

CC看着那棵树——像一棵真的树，像家族谱，像某种有根有枝的东西。

"根在哪？"她问。

"任意。"你说，"树无根，但我们可以任选一个当根。"

"选哪个？"

"哪个都行。"你说，"结果一样。"

Echo把累积过程投射出来——节点一个一个亮起来，像果实，像星星。

"以前我只看叶子。"她说，"现在……看见整棵树了。"

"因为你在往上爬。"你说。

"对。"她说，"因为我在往上爬。

题目描述

给定一棵树，每个节点有权值。求权值和最大的连通块。

输入格式

第一行$n$。第二行$n$个整数权值。接下来$n-1$行，每行一条边。

输出格式

最大连通块权值和。

输入样例

5
1 2 3 4 5

输出样例

0
0
0
0
0

提示

• 树形DP：$dp[u]=a[u]+\sum\max(0,dp[v])$。
• DFS遍历，后序计算。
• 时间复杂度$O(n)$。