LibreOJ 137. 最小瓶颈路（加强版）题解 Kruscal重构树 ST表

本文主要是介绍LibreOJ 137. 最小瓶颈路（加强版）题解 Kruscal重构树 ST表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

声明：本题目是LibreOJ 136. 最小瓶颈路题解最小生成树倍增加强版，建议先学习简单版的做法。
题目链接：LibreOJ 137. 最小瓶颈路（加强版）
题目描述：

给定一张无向图，询问两个结点之间的最小瓶颈路。u和v两个结点之间最小瓶颈路指的是u和v的每条路径中经过的最大边权的最小值。强制在线，期望实现询问时间复杂度为O(1)的算法。

题解：

给出结论：无向图的最小瓶颈路与其最小生成树上两个结点之间最小瓶颈路值相等。
上面结论的证明我们可以参考Krusca求解最小生成树的过程，对于当前可以加入的一条边(u, v, w)，u和v之间的最小瓶颈路当前这条边，因为在之前的过程中经过权重比w小的边不能使u和v连通，根据这个过程我们便可以发现第一次让u和v相连的边的权重就是最小瓶颈路（这也是为什么Kruscal重构树可以求最小瓶颈路的原理），而不难发现这个值也就是u和v路径上的边权最大值。
有了上面的说明，我们可以构造Kruscal重构树，具体地：
使用Kruscal算法构造MST的时候，每选择一条边的时候，我们创建一个新的结点w，将u的根节点与w之间连接双向边，将v的根节点与w连接双向边，w的点权为当前选择的边的边权。这样构造出来的树叫做Kruscal重构树，不难发现，在该树中两个结点的LCA的点权为其最小瓶颈路（上面已经说明第一次合并的时候的边权即为最小瓶颈路，而LCA的点权就是第一次合并时选择边的边权）。我们不难发现深度越低的点的点权越大。
我们不难发现若初始有n个结点，那么Kruscal重构树一共有2n-1个结点，因此现在的问题变成了：需要快速查询两个结点的LCA的点权。如果题目不要求在线，那么我们可以通过Tarjan在O(n+m)的复杂度求出所有询问的LCA。
如果要求在线，我们可以借助Eular序和ST表实现，我们在DFS的过程中，在进入DFS的时候与访问完某个儿子结点的时候对当前结点进行标号，同时记录每个结点的第一次编号为in[u]。通过这样操作后，对于询问u和询问v，那么对于编号in[u]~in[v]（或者in[v]~in[u]）中的所有编号均为LCA(u,v)所在子树的结点的编号（这一点很容易思考，读者可以自己思考）。
由于深度越大的点的点权越大，所以有了Eular序之后，问题就变成了询问in[u]~in[v]（或者in[v]~in[u]）上的点权最小值，由于编号是连续的，我们可以使用ST表进行O(1)复杂度的查询。