P30146

最小生成树

难度 7 级 线段树 优化建图 并查集
讨论 统计 1通过 1提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

给定一张 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)$。

输出

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

样例

样例 1
输入
4
7 6 7 6 4
输出
16
样例 2
输入
8
21 5 28 58 73 32 43 96 72 54 35 28 5
输出
151

提示

  • 对于 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。 题解详见知乎

来源

北大期末考试

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交