[NFLS 1455/2] 动物园 题解

大意

定义 f(u,v)f(u, v) 为所有 uuvv 的路径上, 路径上点权的最小值的最大的路径的最大值.

u,v,uvf(u,v)n(n1)\frac {\sum_{u, v, u \not= v} f(u, v)}{n(n - 1)} .

题解

倒序按照点权加入, 用并查集维护连通性.

每次对于新联通的连通块,如 vv , 对于该点的答案贡献 valu(sizev(sizeusizev))val_u(size_v(size_u - size_v)) ,其中,uu 为当前讨论的点.

(解释: 即里面选一个, 外面选一个)

最后, 再加上 sizeold(u)(sizeusizeold(u))size_{old(u)}(size_u - size_{old(u)}) . (解释: 当前点旧的连通块向新的连通块连边)

技巧

讨论最大值, 最小值时, 可以枚举最大值或最小值, 然后每次讨论时忽略更大或者更小的点.