树的度数优化

题目描述

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

设 $d_i$ 为 $T$ 中顶点 $i$ 的度数,则

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

题目保证答案小于 $2^{63}$。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出答案。

样例

4
3 2 5 2

24

考虑一棵树 $T$,其边为:顶点 $1$ 与 $2$ 相连,顶点 $2$ 与 $4$ 相连,顶点 $4$ 与 $3$ 相连。

此时,$f(T)=1^2\times3+2^2\times2+1^2\times5+2^2\times2=24$。可以证明这就是 $f(T)$ 的最小值。

3
4 3 2

15

7
10 5 10 2 10 13 15

128

数据范围

• $2 \le N \le 2\times10^5$
• $1 \le A_i \le 10^9$
• 输入均为整数。