分数: 550 点
问题陈述
给你一个整数序列 A=(A_1,\ldots,A_N)。对于一棵树 T 与 N 顶点,定义 f(T) 如下:
- 让 d_i 是顶点的度数 i in T。然后, 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