题目描述

X 公司有 $n$ 个员工。这个公司的员工之间的关系构成了一个树形结构。CEO 位于结构的顶端（树的根），他有一些下属（树根的子结点），下属又有下属……最后是一些底层员工（叶结点），没有下属。

这些员工被从 $1$ 到 $n$ 标号，且 CEO 的标号为 1。每个员工有一个 经验值，第 $i$ 个员工的经验值为 $W_i$ 。

这个公司有一个大工程需要完成，所以公司的管理者想要将这个树形结构分裂重组为更小的团队。分裂的方式应遵循以下的规则：

• 任何一个团队至少由一个人组成，每个员工必须属于恰好一个团队。
• 对于任何一个团队，假设团队的成员 按原来的层次等级由低到高排序之后 为 $\{j_1,j_2,j_3,...,j_k\}$ ，那么须满足：对于$\forall i \in [1,k-1]$ 满足 $j_i$ 为 $j_{i+1}$ 的上司。

定义一个团队的总经验值为这个团队的所有成员的经验值的极差，换句话说，就是这个团队里所有成员经验值的最大值减去最小值。整个公司得到的总经验值就是所有团队的经验值之和。

你的任务是求出整个公司可以得到的经验值的最大值。

输入格式

第一行，一个整数 $n$；

第二行，$n$ 个整数：$W_1,W_2,...,W_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$ ，表示 $v$ 是 $u$ 的下属。

输出格式

一个整数表示答案。

7
5 5 3 6 2 3 3
1 6
5 3
1 5
6 2
2 4
6 7

6

提示

样例 1 解释

一种方案是 $\{1,5,3\},\{6,2,4\},\{7\}$。

或者是 $\{1, 5\}, \{3\}, \{6, 2, 4\}, \{7\}$。

数据规模与约定

• 对于大约 $20\%$ 的数据，保证：$n\le 20$。
• 对于大约 $50\%$ 的数据，保证：$n\le 5\times 10^3$。
• 对于另外大约 $10\%$ 的数据，保证：每个员工至多有一个下属。
• 对于所有数据，保证：$1\le n\le 10^5,0\le W_i\le 10^9$。

说明

原题来自：eJOI2017 Problem E Experience

翻译提供： @_Wallace_