#B. Flysky的巴别塔行动

    传统题 1000ms 256MiB

Flysky的巴别塔行动

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

FlyskyFlysky最近沉迷三角洲行动,在新的地图巴别塔中,有一些物资点相连,物资点上可能有一些物品,也可能有敌人。他给地图上的每个物资点都标注了收益aia_i, 这些物资点由n1n - 1条路径相连。

现在FlyskyFlysky位于物资点 11, 他可以在相连的两个物资点上任意移动,物资点可以重复到达。当他到达一个物资点时,他一定会获取上面的收益,同时这个点上面的收益会归零。由于FlyskyFlysky很贪心,他想获得最大的收益,他现在需要你的帮助。

注: 数据保证物资点之间能相互到达。

输入格式

第一行给出一个数 nn (2n2000)(2 ≤ n ≤ 2000)

第二行给出 nn 个数 aia_i, 代表第ii个物资点的收益 (109ai109)(-10^9 ≤ a_i ≤ 10^9)

接下来的 n1n - 1行, 每行给出两个数 uuvv , 代表物资点uu和物资点vv有一条路径相连

输出格式

输出一个数, 表示 FlyskyFlysky 的最大收益

样例

5
3 8 -6 7 3
1 2
1 3
3 4
3 5
15

2024黄冈师范学院第四届『小白杯』ACM程序设计新生赛-热身赛

未参加
状态
已结束
规则
ACM/ICPC
题目
6
开始于
2024-12-1 9:30
结束于
2024-12-1 11:00
持续时间
1.5 小时
主持人
参赛人数
52