F - Tree Degree Optimization

Contest Duration: 2024-06-22(Sat) 12:00 - 2024-06-22(Sat) 13:40 (local time) (100 minutes) Back to Home

F - Tree Degree Optimization Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : $550$ 点

問題文

整数列 $A=(A_1,\ldots,A_N)$ が与えられます。 $N$ 頂点の木 $T$ に対して、 $f(T)$ を以下で定めます。

$T$ の頂点 $i$ の次数を $d_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$

出力

答えを出力せよ。

入力例 1Copy

Copy

4
3 2 5 2

出力例 1Copy

Copy

頂点 $1$ と頂点 $2$ を結ぶ辺、頂点 $2$ と頂点 $4$ を結ぶ辺、頂点 $4$ と頂点 $3$ を結ぶ辺からなるような木 $T$ を考えます。

このとき $f(T) = 1^2\times 3 + 2^2\times 2+1^2\times 5 +2^2\times 2 = 24$ です。これが $f(T)$ の最小値であることが証明できます。

入力例 2Copy

Copy

3
4 3 2

出力例 2Copy

Copy

入力例 3Copy

Copy

7
10 5 10 2 10 13 15

出力例 3Copy

Copy

Score : $550$ points

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 1Copy

Copy

4
3 2 5 2

Sample Output 1Copy

Copy

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 2Copy

Copy

3
4 3 2

Sample Output 2Copy

Copy

Sample Input 3Copy

Copy

7
10 5 10 2 10 13 15

Sample Output 3Copy

Copy