题目描述

题目译自 eJOI2017 Problem E. Experience

X 公司有 $N$ 个员工。该公司有一个严格的等级树状结构——CEO（首席执行官）在最高处（树的根节点），他有一些直属下级，这些直属下级也有一些直属下级，以此类推，直到达到正式员工，他们没有直属下级（也就是树的叶节点）。

这些员工编号为 $1$ 到 $N$。CEO 的编号为 $1$，但是其他编号与等级无关。每个员工都有一定的经验——第 $i$ 位员工的经验用一个非负整数 $W_i$ 来表示。

公司有大量的团体项目需要完成，管理层决定将所有员工分成不同的小组（团队），并满足以下条件：

• 每个团队至少由一人组成，并且每个人都必须属于恰好一个团队。
• 每个团队都必须只由相互之间连续的下属人员组成。一组员工 $j_1,j_2,j_3,j_4,\ldots$ 是一个合法的小组，当且仅当 $j_2$ 是 $j_1$ 的直属下级，$j_3$ 是 $j_2$ 的直属下级，$j_4$ 是 $j_3$ 的直属下级，以此类推。

管理层知道在一个团体项目完成后，执行这个项目的项目组的总经验会加上 $W_{\max}-W_{\min}$，其中 $W_{\max}$ 是小组成员中员工的最大经验，$W_{\min}$ 是小组成员中员工的最小经验。公司的总经验增长等于所有团队的经验增长之和。管理层希望在满足上述两个条件下，通过将员工分成最佳的团队，使公司的总经验增长最大化。

请写一个程序计算这个最大总经验增长值。

输入格式

第一行包含一个正整数 $N$，表示公司的员工总数。

第二行包含 $N$ 个非负整数 $W_1,W_2,\ldots,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\le N\le 10^5,0\le W_i\le 10^9$。

• 对于其中 $20$ 分的数据，$N\le 20$；
• 对于其中 $50$ 分的数据，$N\le 5\ 000$；
• 对于其中 $10$ 分的数据，每个雇员最多有一个直属下级。