「THUPC 2025」图，距离，最优化
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
[AdditionalFile6959.zip](file://AdditionalFile6959.zip?type=additional_file)
#6959. 「THUPC 2025」图，距离，最优化
标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |
题目描述
给定 个非负整数 。
对于任意 个节点的无向连通图 ，将其节点由 至 标号，则其分数定义为
$$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j$$其中 表示图 上 到 的最短路径长度。
你的任务是输出所有 个节点的无向连通图中分数的最大值。
输入格式
本题有多组测试数据。输入的第一行一个整数 表示测试数据组数，接下来依次输入每组测试数据。
每组测试数据的的第一行一个整数 。
每组测试数据的第二行 个整数 描述序列 。
保证所有测试数据的 的和不超过 。
输出格式
对于每组测试数据输出一行一个整数，表示所有无向连通图中分数的最大值。
样例
输入
3
2
1 2
4
1 0 1 1
7
1 2 3 4 5 6 7
输出
2
6
1044
对于第一组测试数据，只有一种合法方案 。
对于第二组测试数据，一个最优方案为 。
题目使用协议
来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。
以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）
- 任何单位或个人都可以免费使用或转载本仓库的题目；
- 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
- 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。