建站实战干货

启动脑子题专场。

首先一个比较关键的地方在于，这个题是环，不是链。想链的情况下怎么做，那么所有路径都已经确定了，我们使用简单数据结构维护一下区间覆盖即可。

发现一个事情，就是最后最优的情况必定至少割掉一条边，我们枚举到底割了哪条边，然后就转化为链的问题了，不难发现每次移动一格总共只会更改 \(O(n)\) 条路径的状态，因此我们用线段树维护这个过程，计算最小值个数即可。