大意
定义 为所有 到 的路径上, 路径上点权的最小值的最大的路径的最大值.
求 .
题解
倒序按照点权加入, 用并查集维护连通性.
每次对于新联通的连通块,如 , 对于该点的答案贡献 ,其中, 为当前讨论的点.
(解释: 即里面选一个, 外面选一个)
最后, 再加上 . (解释: 当前点旧的连通块向新的连通块连边)
技巧
讨论最大值, 最小值时, 可以枚举最大值或最小值, 然后每次讨论时忽略更大或者更小的点.
定义 为所有 到 的路径上, 路径上点权的最小值的最大的路径的最大值.
求 .
倒序按照点权加入, 用并查集维护连通性.
每次对于新联通的连通块,如 , 对于该点的答案贡献 ,其中, 为当前讨论的点.
(解释: 即里面选一个, 外面选一个)
最后, 再加上 . (解释: 当前点旧的连通块向新的连通块连边)
讨论最大值, 最小值时, 可以枚举最大值或最小值, 然后每次讨论时忽略更大或者更小的点.