P7840 "C.E.L.U-03" Reconstruction

Luo Siji recently found that the server runs very slowly, so he plans to reconstruct the entire server network to improve efficiency.

Luo Siji has $n$ servers, and each server has a busyness value $v_i$. Luo Siji will connect them together using $n-1$ network links, so each server will have a degree $d_i$, which is the number of connected links. The total running time of this server network is $\sum\limits_{i=1}^n d_i^2 v_i$. Please minimize this value.

The first line contains one integer, $n$. The second line contains $n$ integers, where the $i$-th integer represents $v_i$.

The first line contains one integer, the answer.

**Sample Explanation:** Connect three edges $1-2, 1-4, 2-3$. The degrees are $2, 2, 1, 1$, respectively. |Testdata ID|$n$|Special Property| |:-:|:-:|:-:| |$1$|$\le5$|None| |$2\sim 3$|$\le300$|None| |$4\sim 5$|$\le3\times10^3$|None| |$6$|$\le3\times10^4$|All $v_i$ are equal| |$7\sim 8$|$\le3\times10^4$|None| |$9\sim 10$|$\le3\times10^5$|None| Constraints: For $100\%$ of the testdata, $1\leq n\le3\times10^5$ and $1\leq v_i\le10^3$. Translated by ChatGPT 5