← 返回题目列表

Codeforces · 1088/F

F. Ehab 和一个奇怪的体重公式

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

给你一棵由 $$$n$$$ 节点组成的树。每个节点 $$$u$$$ 都有一个权重 $$$a_u$$$。保证树中只有一个权重最小的节点。对于每个节点$$$u$$$(权重最小的节点除外),它必须有一个邻居$$$v$$$,使得$$$a_v<a_u$$$。您应该构建一棵树来最小化权重$$$w$$$,计算如下:

- 对于每个节点 $$$u$$$,$$$deg_u \cdot a_u$$$ 被添加到 $$$w$$$ ($$$deg_u$$$ 是包含节点 $$$u$$$ 的边数)。
- 对于每条边 $$$\{ u,v \}$$$, $$$\lceil log_2(dist(u,v)) \rceil \cdot min(a_u,a_v)$$$ 添加到 $$$w$$$,其中 $$$dist(u,v)$$$ 是从 $$$u$$$ 到 $$$v$$$ 的路径中的边数在给定的树中。

输入

第一行包含整数 $$$n$$$ $$$(2 \le n \le 5 \cdot 10^5)$$$,即树中的节点数。

第二行包含 $$$n$$$ 空格分隔的整数 $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$,节点的权重。

接下来的 $$$n-1$$$ 行,每行包含 2 个空格分隔的整数 $$$u$$$ 和 $$$v$$$ $$$(1 \le u,v \le n)$$$,这意味着 $$$u$$$ 和 $$$v$$$ 之间有一条边。

输出

输出一个整数,$$$w$$$ 的最小可能值。

示例

输入 #1

3
1 2 3
1 2
1 3

输出 #1

7

输入 #2

5
4 5 3 7 8
1 2
1 3
3 4
4 5

输出 #2

40

注意

在第一个示例中,树本身最小化了 $$$w$$$ 的值。

在第二个样本中,最优树是: