2024.1.1

100 / 10 / 15, rank 10/35

怎么我这次来打的第一场又是没啥人打导致排名靠前，历史总是惊人的相似。

但是打的还是彩笔，T2 读错题想了半天，开始写暴力了才意识到读错题了 /cf

T3 似乎不太可改

T2 Beautiful World (SDWC2021 Day3T3 美丽的世界)

考虑建图，然后显然一个连通块内要选边数个点，那么只有树与基环树是合法的，那么我们直接考虑两种情况。基环树显然是只有 2 种选择，树可以从每个点开始，有 \(n\) 种选择，总之两者均可以处理出来若干个二元组 \((l, r)\) 表示左部点权值加 \(l\)，右部点权值加 \(r\)。那么现在问题就是，从若干个这样的二元组集合中每个集合选出一个，使得 \((\sum l)(\sum r)\) 最小。

我们考虑将这样的二元组画到平面上。注意到权值相等的点在一条反比例函数的曲线上，这个图像是凸的，也就是说任意两点之间的边上的点的权值一定是比两个端点大的，那么也就是说将这些点求出一个凸包来，实际上只有左下凸包上的点可能成为最小值。那么我们实际上只需要最后将所有的点合并成一个点集后，这个点集的凸包上的点即可。而注意到合并过程就是两个点集的闵可夫斯基和，于是我们只需要对集合的凸包做闵可夫斯基和即可。分治一下或启发式合并容易做到 \(O(n \log n)\)。