CF1656F Parametric MST

给定 $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)$ 是否有上界，如果有，请输出其所能取得的最大值。

输入包含多组测试数据。第一行包含一个整数 $T$（$1 \leq T \leq 10^4$），表示测试数据的组数。接下来每组测试数据描述如下： 每组测试数据的第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$），表示图的顶点数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-10^6 \leq a_i \leq 10^6$）。 所有测试数据中 $n$ 的总和不超过 $2 \times 10^5$。

对于每组测试数据，输出一行，表示 $f(t)$ 的最大值（可以证明该值为整数）；如果 $f(t)$ 没有上界，则输出 INF。

由 ChatGPT 4.1 翻译