【题解】Solution Set - NOIP2024集训Day50 图的连通性相关

https://www.becoder.com.cn/contest/5618

「JSOI2012」越狱老虎桥

简述题意：

题目大意：给定一张图，A 先添加 \(1\) 条边，B 再删去一条边使得图不连通，A 要最大化删除边的权值，B 要最小化删除边的权值，问最终的权值是多少。

显然，B 删去的一定是桥。我们先边双缩点，A 加入的边会让树上的任意一条链上的边全部失效。

然后 A 一定会去让这条链覆盖到所有较小的边。

考虑从小到大考虑可以覆盖到的边，动态维护满足满足当前这些边的最小的链。加边就是看当前的链的两端中的某一端（如果都行那就去深度较大的）其子树中完全包含了新加边的两端，如果满足就将这个端点移动到新加边的两端深度较大的一段。最小覆盖的链初始为 \((1,1)\)。

20min