ABC301Ex

· · 题解

因为本题要求的是最小瓶颈路，可以考虑建出原图的最小生成树，那么最小瓶颈一定为 MST 上两点路径边权的最大值。

考虑修改一条边会有什么影响，可以发现，除非你修改的这条边恰为 s 到 t 的瓶颈，你的修改是一定没有贡献的。若它为瓶颈边，设其权值为 w，则若加入所有权值 \le w 的非树边进去后 (s,t) 能联通，答案仍不变。

具体维护时，我们可以将所有边按 w 排序，每次将非树边的 (u,v) 在树上的路径上的所有点合并进一个并查集中，这样，每次断开树边 (x,y) 时（设 x 为深度较大的那个点），我们只需查询 x 是否与它的祖先中任意一个在同一个并查集内即可。

Code