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.

时空限制

1S/512M

题目描述

树的高度应该怎么测量？

A.拿一把超长的尺子

B.利用相似三角形和影子长度

C.深度优先搜索

现在，有 $n$ 片空地，每个空地上都有一棵树。这 $n$ 片空地通过 $n-1$ 条双向道路连接成了一个以 $1$ 号空地为根的有根树。 其中，第 $i$ 棵树的初始高度为 $h_i$。

你可以执行以下操作任意次：

• 选择一个节点 $i$，使其高度增加 $1$，即 $h_i \leftarrow h_i + 1$。

为了让这 $n$ 棵树看起来具有某种“层次感”，你需要通过执行若干次操作，使得对于任意两个节点 $u$ 和 $v$，如果 $u$ 是 $v$ 的祖先（不包括 $v$ 本身），则修改后的高度必须满足 $h_u>h_v$。

请计算出至少需要执行多少次操作。

格式

输入格式

第一行包含一个整数 $n$，表示空地的数量。

第二行包含 $n$ 个整数 $h_1, h_2, \dots, h_n$，中间用空格隔开，表示每棵树的初始高度。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示 $u$ 号空地与 $v$ 号空地之间有一条双向道路。

输出格式

输出一个整数，表示最少的操作次数。

样例

样例输入 #1

4
5 2 8 3
1 2
1 3
3 4

样例输出 #1

4

样例输入 #2

3
10 10 10
1 2
2 3

样例输出 #2

3

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^5$，$1 \le h_i \le 10^9$。