题目描述

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

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

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

题目使用协议

来自 THUPC2025（2025年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2025 官方仓库（https://gitlink.org.cn/thusaa/thupc2025final）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库地址 或 算协公开仓库链接。