CF1976F Remove Bridges

紊莫 · 2024-07-01 12:24:03 · 题解

标签：贪心

给出一种代码略长但是无脑的做法。

首先发现第一次一定要连接 1 号点和另一个点，那么一定是连接深度最大的点，我们定义 val_i 表示 i 到根的路径上桥边的个数，也就是说选出 val 最大的位置，然后我们暴力去更新它到根上的所有边，直到遇到非桥边或者到根。

这样的话复杂度是均摊 O(n) 的，因为每条边只会被遍历一次。

然后对于剩下的操作，我们显然每次取出两个 val 最大的值，然后将这条路径上的点暴力更新，证明其他题解已有，不再赘述。

此处我们可以直接用线段树来维护 val 值，首先按照 dfs 序拍平序列，然后每一次标记一条边，就会把下面子树的 val 全都减一，这样就好了。

时间复杂度 O(n \log n)，代码是 VP 的时候写的，比较混乱。