CF1656F.Parametric MST

You are given $n$ integers $a_1, a_2, \ldots, a_n$. For any real number $t$, consider the complete weighted graph on $n$ vertices $K_n(t)$ with weight of the edge between vertices $i$ and $j$ equal to $w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j)$.

Let $f(t)$ be the cost of the minimum spanning tree of $K_n(t)$. Determine whether $f(t)$ is bounded above and, if so, output the maximum value it attains.

给你 $n$ 个整数 $a_1, a_2, \ldots, a_n$。对于任意实数 $t$，考虑一个具有 $n$ 个顶点的完全加权图 $K_n(t)$，其中顶点 $i$ 与顶点 $j$ 之间的边的权重为 $w_{ij}(t) = a_i \cdot a_j + t \cdot (a_i + a_j)$。

令 $f(t)$ 表示图 $K_n(t)$ 的最小生成树 的总权重。判断 $f(t)$ 是否有上界；若存在上界，则输出其能达到的最大值。

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \leq T \leq 10^4$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \leq n \leq 2 \cdot 10^5$) — the number of vertices of the graph.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-10^6 \leq a_i \leq 10^6$).

The sum of $n$ for all test cases is at most $2 \cdot 10^5$.

输入包含多个测试用例。第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \cdot 10^5$），表示图中顶点的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^6 \leq a_i \leq 10^6$）。

所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, print a single line with the maximum value of $f(t)$ (it can be shown that it is an integer), or INF if $f(t)$ is not bounded above.

对于每个测试用例，输出一行，包含 $f(t)$ 的最大值（可以证明该值为整数）；若 $f(t)$ 无上界，则输出 INF。