[eJOI2017] 经验

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](www.ejoi.org) Problem E [Experience](http://ejoi.org/wp-content/themes/ejoi/assets/pdfs/tasks_day_2/EN/experience_statement-en.pdf) 翻译提供： @[```_Wallace_```](https://www.luogu.com.cn/user/61430)