Kruskal 重构树
这是一种用于处理与最大/最小边权相关的一个数据结构。
其与 kruskal 做最小生成树的过程是类似的,我们考虑其过程:
按边权排序,利用并查集维护连通性,进行合并。
如果我们在合并时,新建一个节点,其权值为当前处理的边的权值,并将合并的两个节点都连向新建的节点,那么就可以得到一颗重构树。
例如下列数据生成的重构树:
4
1 4 2
2 3 4
1 3 1
3 4 3
黑色代表节点编号,红色代表其权值。
其满足一些性质:
-
这是一个二叉树,也是一个二叉堆
-
两点 \(\mathrm{LCA}\) 的权值即是这两点联通的 最小/最大 代价/时间。
-
对于一个限制,找到某个点最高的祖先 \(S\) 满足这个限制,那么 \(S\) 所在子树都满足此限制,并且此子树下所有叶节点在此限制下全部联通。
由于这些性质,kruskal 重构树常常与树剖/树上倍增放一起,做到每次 \(O(\log n)\) 的神秘操作。
以 Qpwoeirut and Vertices - 洛谷 为例:
给出 \(n\) 个点,\(m\) 条边的不带权无向连通图,\(q\) 次询问至少要加完前多少条边 \([L, R]\) 中的所有节点联通。
这是非常板的题,边权也就是其编号。
设 \(f(x)\) 表示 \(x\) 和 \(x + 1\) 联通的时间,那么所求也就是 \(\max_{x = L}^{R - 1} f(x)\),这只需要求出 \(f(x)\) 随便维护一下即可。
那么求 \(x, x + 1\) 的联通时间,找到他们在重构树上的 \(\mathrm{LCA}\),返回其编号即可。
或许其考点就是知不知道重构树,如果会了重构树,那么就简单了。
按照边权从大到小建出重构树,那么在当前水位下可联通的部分(整棵子树)也就很好求。
求这部分到固定的终点的最短路径?跑一次 DJK,然后把重构树看作一颗线段树,节点保存的也就是子树内最小的距离,在查询的时候利用倍增跳一跳就行了。
标签:重构,联通,Kruskal,30,最小,节点,边权 From: https://www.cnblogs.com/jeefy/p/17761104.html