← 返回题目列表

AtCoder · abc359_f

I. 树度优化

中文机器翻译题面 查看原题

分数: 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