题意

询问两点之间的所有路径中最长的边最小是多少。

分析

显然,要使得任意两点之间的最长边的长度最小,是在最小生成树上跑。

利用最小生成树,在边上建一个虚点,即利用Kruskal重构树。

利用重构树的性质,父亲的权值\(\ge\)孩子,于是两点之间的最长边的最小值就是两点在重构树上的lca,再倍增一下即可。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注