CF1656F

题目大意：

一张无向完全图，节点 \(i\) 的点权为 \(a_i\)。每条边的边权由一个函数给出，\(W(u,v,t)=a_ua_v+t\times(a_u+a_v)\)，其中 \(t\) 是一个尚未确定任意实数，且对于所有边都是一致的。显然如果固定 \(t\) 就存在一颗最小生成树，于是定义 \(F(t)\) 等于此 \(t\) 下最小生成树的边权和。输出 \(F\) 的最大值，如果不存在最大值，输出 \(inf\)。\(n\leq2\times10^5,a\leq10^6\)。

自然地对原图的每个生成树考虑，它的边权和显然是随 \(t\) 变化的一次函数，于是 \(F\) 可以被描述成所有生成树直线的取 \(\max\)，显然这样产生的函数是具有凸性的。

于是这个题的做法变得清晰，先判断斜率最大和最小的两根直线是否能使得凸包具有最大值，即判断斜率是否同号。如果同号说明不存在最大值，否则在凸包上二分就可以找到最值了。至于如何找到这两个直线，直接用 Prim 贪心即可。

然后思考如何在一个固定的 \(t\) 下找到最小生成树。首先原式可以变形成 \((a_u+t)(a_v+t)-t^2\)，这就好办多了，\(-t^2\) 可以直接忽略不管，剩下的部分直接 Prim On 贪过去，每次用已经确定点集的最大最小值*未确定点集的最大最小值，全判一遍就行，这样比较省事，如果判正负精细实现可能会比较麻烦。似乎 Deque 就可以，也可能是我笨比了。