D. 模图最小生成树

题目翻译

给定一张包含 $n$ 个节点的完全无向图，第 $i$ 个节点拥有权值 $p_i$。

连接节点 $x$ 与节点 $y$ 的边权定义为：

你需要求出选取 $n-1$ 条边、将所有 $n$ 个节点连通的最小总边权，也就是这张图的最小生成树（MST）边权和。

输入格式

每个测试点包含多组测试数据。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例数量。

每组测试用例：

• 第一行一个整数 $n$（$1\le n\le 5\cdot 10^5$），表示节点数量；
• 第二行 $n$ 个整数 $p_1,p_2,\dots,p_n$（$1\le p_i\le 5\cdot 10^5$），表示每个节点的权值。

保证：

• 所有测试用例的 $n$ 之和不超过 $5\cdot 10^5$；
• 所有测试用例的 $\max(p_1,p_2,\dots,p_n)$ 之和不超过 $5\cdot 10^5$。

输出格式

对于每组测试用例，输出一行一个整数，表示最小生成树的总权值。

输入样例

4
5
4 3 3 4 4
10
2 10 3 2 9 9 4 6 4 6
12
33 56 48 41 89 73 99 150 55 100 111 130
7
11 45 14 19 19 8 10

输出样例

1
0
44
10

样例解释

第一个测试用例： 一种最优连边方案为 $(1,2),(1,4),(1,5),(2,3)$。 其中边 $(1,2)$ 的权值为：

其余所有边的权值均为 $0$，因此总权值为 $1$。