#8958. 「洛谷 P12052」[THUPC 2025 决赛] 图，距离，最优化 暂未评定

给定 个非负整数 。

对于任意 个节点的无向连通图 ，将其节点由 至 标号，则其分数定义为：

其中 表示图 上 到 的最短路径长度。

你的任务是输出所有 个节点的无向连通图中分数的最大值。

本题有多组测试数据。输入的第一行一个整数 表示测试数据组数，接下来依次输入每组测试数据。

每组测试数据的的第一行一个整数 。

每组测试数据的第二行 个整数 描述序列 。

保证所有测试数据的 的和不超过 。

对于每组测试数据输出一行一个整数，表示所有无向连通图中分数的最大值。

样例输入 1

3
2
1 2
4
1 0 1 1
7
1 2 3 4 5 6 7

样例输出 1

2
6
1044

样例 #1 解释

对于第一组测试数据，只有一种合法方案 。

对于第二组测试数据，一个最优方案为 。

来源与致谢

来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。

数据、题面、标程、题解等请参阅 THUPC 官方仓库 https://thusaac.com/public。