AT_abc359_f [ABC359F] Tree Degree Optimization

题目描述

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

输入格式

输入从标准输入中以如下格式给出：

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
3 2 5 2

输出 #1

24

输入输出样例 #2

输入 #2

3
4 3 2

输出 #2

15

输入输出样例 #3

输入 #3

7
10 5 10 2 10 13 15

输出 #3

128

说明/提示

约束条件

• $2\leq N\leq 2\times 10^5$
• $1\leq A_i\leq 10^9$
• 输入的所有数均为整数

样例解释 1

考虑如下的树 $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)$ 的最小值。

由 ChatGPT 4.1 翻译