克鲁斯卡尔重构树小结

总结

定义

克鲁斯卡尔重构树可以维护诸如“查询从某个点出发经过边权不超过$w$的边最远所能到达的节点”或“从某点到某点所有路径的最长边的最小值”之类的问题。

总之，算法处理范围有限，且多为同时包含“最大最小”、离线可二分的题目。
可与数据结构结合，以维护更复杂的数据结构。
它可以在线回答，复杂度为$O(logn)$。

构建

把边权从大到小排序，用给两端点（两个联通块）新建一个权值为边权的共同父亲，来代表给它们加了一条边。

性质

• 树上除叶子结点以外的点都对应着原来生成树中的边，叶子结点就是原来生成树上的节点。
• 由于新点的创建顺序与原来生成树上边权的大小有关（从大到小），可以发现，从每个点到根节点上除叶子结点外按顺序访问到的点的点权是单调的。
• 出于$kruskal$算法贪心的性质，两个点$u$和$v$的$lca$的点权就对应着它们最小生成树上的瓶颈。
• 实际上这棵树就是一个二叉堆。

相关题目

• [bzoj3732]network
• [NOI2018]归程
• [ONTAK2010]Peaks加强版