给你一棵由 $$$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$$$ 的值。
在第二个样本中,最优树是: