回顾一下 Kruskal 最小生成树算法的过程:
算法流程:
1. 将所有边按照边权升序排序 $O(m \log m)$。
2. 枚举每条边 $(a,b)$,如果这两个点不连通则把这条边加入最小生成树。
然后今天遇到了一道这样的题目:求出从某个点出发,经过边权不超过 w 的边能到达的节点。
算法1
暴力解决一切,直接从这个点 dfs
即可,复杂度为 $O(n)$。
算法2
引入 Kruskal 重构树。
对于原图,我们先找出它的一棵最小生成树,这里使用 Kruskal 算法。
对于最小生成树中的边,我们以边权为关键字升序排序,并依次进行处理。
进行一个类似于并查集合并的过程,如果当前边连接的两个点不在同一个子树内,则新建一个点,点权为该边边权,它的左右儿子分别为两个点所在子树的根。(由于作者美术细胞受到宇宙射线的辐射坏死,这里就不放图了)
这个 Kruskal 重构树有一个十分优美的性质,那就是对于任何非叶子节点,它的子树内所有点权都小于等于它!
于是我们要找原图中 $u$ 出发不经过大于 $w$ 的边能到达的店,相当于我们在重构树上一路往祖先跳,直到找到深度最浅的一个点权 $\leq w$ 的点,它子树内所有点就是答案。
综上所述,预处理即 $O(m \log m)$,询问可以做到 $\log$ 级别,用倍增处理一下可以优化。