103595: [Atcoder]ABC359 F - Tree Degree Optimization

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

问题描述

你被给定一个整数序列 $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}$。

限制条件

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i \leq 10^9$
• 所有输入值都是整数。

输入

输入通过标准输入给出以下格式：

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

输出

打印答案。

样例输入 1

4
3 2 5 2

样例输出 1

24

考虑一棵树 $T$，有边连接顶点 $1$ 和 $2$，边连接顶点 $2$ 和 $4$，以及边连接顶点 $4$ 和 $3$。

那么，$f(T) = 1^2\times 3 + 2^2\times 2 + 1^2\times 5 + 2^2\times 2 = 24$。可以证明这是 $f(T)$ 的最小值。

样例输入 2

3
4 3 2

样例输出 2

15

样例输入 3

7
10 5 10 2 10 13 15

样例输出 3

128