代码有点史，懒得写了。
你注意到一件事情就是，先随便拎出一棵最小生成树，我们将边分为在这棵树上的边和不在这棵树上的边，那么我们分别考虑。
- 对于树边，考虑所有包含它的非树边最小的那一条就是其上界。
- 对于非树边，其两个端点之间的树边路径上边权最小的那一条就是其上界。
容易用树链剖分做到 \(O(n \log^2 n)\)，如果会更高明的维护技巧可以做到 \(O(n \log n)\)。
这种最小生成树的题的一个经典套路。
代码有点史，懒得写了。
你注意到一件事情就是，先随便拎出一棵最小生成树，我们将边分为在这棵树上的边和不在这棵树上的边，那么我们分别考虑。
容易用树链剖分做到 \(O(n \log^2 n)\)，如果会更高明的维护技巧可以做到 \(O(n \log n)\)。
这种最小生成树的题的一个经典套路。