最大子树和

题意概述

有一棵树，上面连着 \(n\) 朵"花"（节点），有 \(n-1\) 条枝条（无向边）把它们连成一棵树（保证连通、无环）。 每朵花有一个"美丽指数"（可以是负数）。

你可以反复做"修剪"操作：砍掉一条枝条，把树分成两部分，然后扔掉其中一部分。 多次修剪后，最终只剩下一棵连通的子树（也可能只有一个点）。 目标：让这棵留下来的子树里所有花的美丽指数之和最大。

换句话说：从整棵树里选一个连通子树，使其节点权值之和最大。

输入格式

1. 第一行：一个整数 \(n\)（节点数）。
2. 第二行：\(n\) 个整数，第 \(i\) 个是第 \(i\) 朵花的美丽指数。
3. 接下来 \(n-1\) 行：每行两个整数 \(a, b\)，表示 \(a\) 和 \(b\) 之间有一条枝条（无向边）。

输出格式

输出一个整数：能得到的最大"美丽指数"之和。

样例

输入

7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7

输出

3

解释 选取由节点 \(4,5,6,7\) 组成的连通子树（或其它等价最优连通块），和为 \(1+1+1+0=3\)，为最大值。

约束

• \(1 \le n \le 16000\)
• 节点权值与答案的绝对值不超过 \(2147483647\)
• 输入保证构成一棵树（连通、无环）