货车运输

借这一道题目来介绍一下最小瓶颈路和Kruscal重构树

首先本来这道题目我其实是没看出来是最大生成树的（因为不知道上面两个东西），然后我想的是二分，当然也可以做，但是复杂度多一个\(log\)

对上面两个东西的介绍见OI-wiki

下面是一些解释

最小瓶颈路的性质的第一句话说“根据最小生成树定义”，其实这个根据定义是出不来的，我们需要证明，而且这个证明不是简单的反证法就可以证明成功的，要用比较复杂的反证

我们考虑某一对点\((u,v)\)，在MST上其存在且仅存在一条路径，设这条路径的边权的最小值为\(a\)；假设在原图中\((u,v)\)存在另一条路径，设这条路径的边权的最小值为\(b\)，且\(b>a\)，则我们考虑这条路径中不在MST中的边

对这样的一条边，我们考虑Kruscal算法的过程，当遍历到这条边的时候，我们没有将这条边加入Kruscal，因为这条边的两个端点已经存在一条路径了，而且这条路径上的每一条边都是最终MST上的边。也就是说，我们可以将我们找到的任意一条其他的非MST路径上不是MST中的边全部换成若干条MST上的边，而且边权最小值会变大（或者至少不会变差），所以最后所有边都是MST上的边而且答案不会更劣；由于MST上\((u,v)\)只有一条路径，所以说这就是最优的答案

我们以上的证明过程也说明我们随便求一个MST就好了

然后这道题目只会用到最小瓶颈路

接下来介绍一下Kruscal重构树

定义中说“得到了一颗恰有\(n\)个叶子的二叉树”，实际上这些叶子全部都是原图中的点（也就是说新添加的点都不是叶子），这个用数学归纳法可以证明；“非叶子节点恰有两个儿子”也可以用数学归纳法证明

那么为什么

第一个等号见上文证明；第二个等号我们来考虑Kruscal的过程

对于\((u,v)\)在MST上的路径，我们找出其边权最大的边，这条边是这条路径中最后被添加到MST中的边

在添加这条边之前，\(u\)和\(v\)各自在两个连通块中，而且这两个连通块都是树，\(u\)或者\(v\)一直往上面走最终会走到各自连通块的根节点；添加这条边之后，我们连接了两个连通块（树）的根节点，并且将这两个根结点作为新连通块根节点的左右儿子，所以这个时候\(u\)和\(v\)各自往上面走，就会走到这个新连通块的根节点，所以这个根节点就是两者的LCA，且这个LCA的点权刚好是我们添加的最后一条边的边权，也就是路径的最大值

我们还可以发现，最终得到的Kruscal重构树，父亲的权值一定不会低于两个儿子的权值