P12052 [THUPC 2025 决赛] 图，距离，最优化

给定 $n$ 个非负整数 $x_1,x_2,\dots,x_n$。 对于任意 $n$ 个节点的无向连通图 $G$，将其节点由 $1$ 至 $n$ 标号，则其分数定义为： $$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j$$ 其中 $\text{dist}_G(i,j)$ 表示图 $G$ 上 $i$ 到 $j$ 的最短路径长度。 你的任务是输出所有 $n$ 个节点的无向连通图中分数的最大值。

本题有多组测试数据。输入的第一行一个整数 $t\ (1 \le t \le 300)$ 表示测试数据组数，接下来依次输入每组测试数据。 每组测试数据的的第一行一个整数 $n\ (1 \le n \le 300)$。 每组测试数据的第二行 $n$ 个整数 $x_1,x_2,\dots,x_n\ (0 \le x_i \le 2000)$ 描述序列 $x$。 保证所有测试数据的 $n$ 的和不超过 $300$。

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

### 样例 #1 解释 对于第一组测试数据，只有一种合法方案 $G = \{(1,2)\}$。 对于第二组测试数据，一个最优方案为 $G = \{(1,2),(2,3),(2,4)\}$。 ### 来源与致谢 来自 THUPC2025（2025 年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。 数据、题面、标程、题解等请参阅 THUPC 官方仓库 。