You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

【问题描述】

在M星球上有n个国家，编号从1到n，第i个国家建造在高度为hi的山上，这些国家之间由n-1条特殊的通道的连接，随着M星人对国际间交流的需求越来越迫切，这n个国王计划合资修建一些特殊的信号塔用于国际间通信。这些特殊的信号塔只能通过n-1条特殊的通道传播信号，并且要修建一座强度为e 的信号塔，需要花费e枚金币的代价。

对于一对信号塔，如果它们所在的点u，v之间的简单路径经过点x（x可以是路径的两个端点），那么x就可以接收到min(e​~u~​,e​~v~​)强度的信号。对于一个高度为h~x~的国家，它需要接收到强度超过h~x~的信号才可以进行与其他国家之间的通信。

现在，这群国王想知道要想使所有国家都可以进行通信，至少需要花费多少金币，由于这群国王的数学不是很好，他们把这个任务推给了你。

【输入】

第一行包含了1个整数n(2≤n≤2×10​^5^​)，表示M星球上国家的数量。

第二行包含了n个整数hi(1≤h​~i~​≤10​^9^​)，表示第i个国家的高度。

之后的n−1行，每行包含2个整数ui，vi，表示国家ui，vi之间存在一条特殊通道，保证这n个国家之间联通。

【输出】

输出一行一个整数，表示使得所有国家能进行通信要花费的最少金币数。

【样例输入1】

3
1 2 1
1 2
2 3

【样例输出2】

4

【样例输入1】

5
1 3 3 1 3
1 3
5 4
4 3
2 3

【样例输出2】

7

数据规模