← 返回题目列表

Codeforces · 1637/F

F. 塔

中文机器翻译题面 查看原题

给你一棵树,其顶点为 $$$n$$$,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 个顶点的高度为 $$$h_i$$$。您可以将任意数量的塔放置到顶点中,对于每个塔,您可以选择将其放置在哪个顶点中,以及选择其效率。以 $$$e$$$ 效率建立一座塔需要花费 $$$e$$$ 硬币,其中 $$$e > 0$$$。

如果对于顶点 $$$u$$$ 和 $$$v$$$ 处的一对塔($$$u \neq v$$$,但允许 $$$x = u$$$ 或 $$$x = v$$$),则认为顶点 $$$x$$$ 收到信号,效率 $$$e_u$$$ 和$$$e_v$$$ 分别满足 $$$\min(e_u, e_v) \geq h_x$$$ 和 $$$x$$$ 位于 $$$u$$$ 和 $$$v$$$ 之间的路径上。

找到建立塔所需的最少硬币数量,以便您可以在所有顶点收到信号。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 200\,000$$$) — 树中的顶点数。

第二行包含 $$$n$$$ 整数 $$$h_i$$$ ($$$1 \le h_i \le 10^9$$$) — 顶点的高度。

接下来的 $$$n - 1$$$ 行均包含一对数字 $$$v_i, u_i$$$ ($$$1 \le v_i, u_i \le n$$$) - 树的一条边。保证给定的边形成一棵树。

输出

打印一个整数——所需的最少硬币数量。

示例

输入 #1

3
1 2 1
1 2
2 3

输出 #1

4

输入 #2

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

输出 #2

7

输入 #3

2
6 1
1 2

输出 #3

12

注意

在第一个测试用例中,最佳选择是在顶点 $$$1$$$ 和 $$$3$$$ 处安装两个效率为 $$$2$$$ 的塔。

在第二个测试用例中,最佳选择是在顶点 $$$1$$$ 处安装效率为 $$$1$$$ 的塔,并在顶点 $$$2$$$ 和 $$$5$$$ 处安装效率为 $$$3$$$ 的两个塔。

在第三个测试用例中,最佳选择是在顶点 $$$1$$$ 和 $$$2$$$ 处安装两个效率为 $$$6$$$ 的塔。