Score : $550$ points

问题陈述

给定一个整数序列 $A=(A_1,\ldots,A_N)$。对于一个有 $N$ 个顶点的树 $T$，定义 $f(T)$ 如下：

• 设 $d_i$ 为树 $T$ 中顶点 $i$ 的度数。那么，$f(T)=\sum_{i=1}^N {d_i}^2 A_i$。

找出 $f(T)$ 的最小可能值。

约束条件保证答案小于 $2^{63}$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given a sequence of integers $A=(A_1,\ldots,A_N)$. For a tree $T$ with $N$ vertices, define $f(T)$ as follows:

• Let $d_i$ be the degree of vertex $i$ in $T$. Then, $f(T)=\sum_{i=1}^N {d_i}^2 A_i$.

Find the minimum possible value of $f(T)$.

The constraints guarantee the answer to be less than $2^{63}$.

Constraints

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the answer.

Sample Input 1

4
3 2 5 2

Sample Output 1

24

Consider a tree $T$ with an edge connecting vertices $1$ and $2$, an edge connecting vertices $2$ and $4$, and an edge connecting vertices $4$ and $3$.

Then, $f(T) = 1^2\times 3 + 2^2\times 2 + 1^2\times 5 + 2^2\times 2 = 24$. It can be proven that this is the minimum value of $f(T)$.

Sample Input 2

3
4 3 2

Sample Output 2

15

Sample Input 3

7
10 5 10 2 10 13 15

Sample Output 3

128