题目描述

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

输出格式

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

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

2
6
1044

提示

样例 #1 解释

对于第一组测试数据，只有一种合法方案 $G = \{(1,2)\}$。

对于第二组测试数据，一个最优方案为 $G = \{(1,2),(2,3),(2,4)\}$。

来源与致谢

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

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