借这一道题目来介绍一下最小瓶颈路和Kruscal重构树首先本来这道题目我其实是没看出来是最大生成树的（因为不知道上面两个东西），然后我想的是二分，当然也可以做，但是复杂度多一个\(log\)对上面两个东西的介绍见OI-wiki下面是一些解释最小瓶颈路的性质的第一句话说“根据最小生成树定

这一道题目，我们看到\(q\)非常小，所以可以尝试从\(q\)入手对每种组合，我们想要求出必须选择这些组合的MST，也即“含有必须边的MST”（尽管现在还不清楚每个组合的边是什么，下文会说）这种情况跟陈立杰出的那道“tree”非常像，我们只用把必须边的边权缩小放到前面然后跑Kruscal即可那为

来严格证明一下做法我们利用数学归纳法证明，过程很像“推论+数归证明Kruscal”假设我们按照书上这么添加后，执行Kruscal当前执行到\(i\)这条边，已经选上的边都是最开始的树边，已经循环过但没选上的边都是添加的非树边假设\(i\)是添加的边，那么\(i\)一定不会被选上，因为此时已经选上