/ 
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
出力
答えを出力せよ。
入力例 1
4 3 2 5 2
出力例 1
24
頂点 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) の最小値であることが証明できます。
入力例 2
3 4 3 2
出力例 2
15
入力例 3
7 10 5 10 2 10 13 15
出力例 3
128
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 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