30146 - 最小生成树

给定一张 n 个点的完全图，点的编号为 1 \sim n，对于两个点 i, j (i \neq j)，它们之间的边权为 a_{i+j}。请你求解这张图的最小生成树，你只需要给出最小生成树的边权和即可。

第一行一个正整数 n (2 \leq n \leq 2 \times 10^5) 表示图的点数。

第二行 2n - 3 个正整数，表示 $a3 \sim a{2n-1} (1 \leq a_i \leq 10^9)$。

一行一个正整数表示答案。

• 对于 20\% 的测试点：n \leq 1000。
• 对于 30\% 的测试点：n \leq 10000。
• 对于另外 20\% 的测试点：a_i 在 [1, 10^9] 中均匀随机生成。
• 对于所有测试点：1 \leq n \leq 2 \times 10^5，1 \leq a_i \leq 10^9。 题解详见知乎

北大期末考试