ABC359_F Tree Degree Optimization

题目描述

给你一个整数序列A=(A1,…,AN)。对于一棵有N个顶点的树T，定义f(T)如下：

• 设di​是T中顶点i的度数。那么，f(T)=$\sum_{i=1}^{N}{d_i}^2A_i$

求f(T)的最小可能值。

约束条件保证答案小于$2^{63}$。

输入描述

第一行一个整数N

第二行N个数字$A_1,A_2...A_N$

数据范围：

• 2≤N≤2×$10^5$
• 1≤$A_i$≤$10^9$

输出描述

打印答案

提示

样例1解释：

考虑一棵树T有一条边连接顶点1和2，一条边连接顶点2和4，一条边连接顶点4和3。

那么，f(T)=$1^2$×3+$2^2$×2+$1^2$×5+$2^2$×2=24。可以证明这是f(T)的最小值。