← 返回题目列表

Codeforces · 1656/F

F. 参数 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 \cdot 10^5$$$) — 图的顶点数。

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

所有测试用例的 $$$n$$$ 总和最多为 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一行,其中最大值为 $$$f(t)$$$(可以证明它是一个整数),如果 $$$f(t)$$$ 不受上面限制,则打印 INF。

示例

输入 #1

5
2
1 0
2
-1 1
3
1 -1 -2
3
3 -1 -2
4
1 2 3 -4

输出 #1

INF
-1
INF
-6
-18