CF827D Best Edge Weight

发表于 分类于 ， ， 阅读次数：

题意：给出一张无向带权连通图。

对于图中的每条边,求出边权最大为多少时，它还必定能出现在最小生成树上。若总是能出现，回答 。

，时限 。

先求出原图的最小生成树。分类讨论。

  • 边 不在最小生成树上。

    根据 LCT 维护动态生成树的经验，若该边严格小于生成树 间的任何一条边，就能够取而代之。

    那么这就是个简单的链 问题，随手倍增一下就是了。

  • 边 在最小生成树上。

    相反，若所有的非树边无法取代该边，则其就必定在最小生成树上。

    我们将所有的非树边 的权值，写在生成树 间的所有边上，则某条边的权值上限就是其上数字的 再 。

    可以视作链取问题，直接树剖是 的。

    注意到可以离线，将操作按照权值升序排序，这就满足每条边第一次被覆盖到时，就是答案。

    已经得到了答案的边，就无需再关注，可以用并查集缩起来。（一个连通块的根设为最浅点，可以支持快速跳过已经被覆盖的边）

    由于每条边只会被覆盖一次，复杂度 。