算法基本概念

\(Kruskal\) 重构树是一种巧妙处理图上边权限制的算法，用某种方法建立出一颗具有特殊性质的树，通过树上的一些操作巧妙处理图上的限制，用起来感觉真的挺妙的，把二者很完美地结合了起来。

主要思想基于 \(kruskal\) 求最小生成树的方法，二者的构建过程是比较相似的，一般地，我们按以下步骤来对一个图构建 \(kruskal\) 重构树。

先按照边权从小到大排序，用并查集维护连通性，若当前的边 \(u->v\) 边权是 \(w\) ，且 \(u,v\) 不属于同一联通块，就新建一个结点 \(cnt\) ，由 \(cnt\) 向 \(u,v\) 当前并查集维护的根节点连一条边，新建的节点作为新的联通块中的根节点，按照这个过程考虑完所有的边之后，得到的就是原图的 \(kruskal\) 重构树了。

以上大概是一些算法概念和定义的介绍，如果读者感觉不知所云或者不知道怎么运用，请继续看下去，下面我们通过一些例题来感受重构树的精妙所在。

里面用到的结论，笔者也会进行一些感性的证明，让读者可以更好地理解。

[LOJ137] 最小瓶颈路 加强版

给定一个 \(n\) 个点 \(m\) 条边的无向连通图，编号为 \(1\) 到 \(n\) ，没有自环，可能有重边，每一条边有一个正权值 \(w\) 。

给出 \(q\) 个询问，每次给出两个不同的点 \(u\) 和 \(v\) ，求一条从 \(u\) 到 \(v\) 的路径上边权的最大值最小是多少。

\(1\le n,m \le 1e5\) , \(1\le q \le 1e7\)

在没有学习本算法之前，一个比较自然的想法是，考虑贪心，开始所有点不连通，我们由小到大对边进行枚举，枚举到一条边后联通它所连接的两个节点，并查集维护一下连通性，枚举到某条边后 \(