CF603E Pastoral Oddities

· · 题解

正向推导一波。仅仅代表我的思考路径。可能有些繁琐。

首先考虑静态无权怎么判断合法。对于一棵树，我们从叶子结点开始往上推。叶节点的父边是必选的，然后再往上可以依次确定每个点的父边是否选择。这棵树是合法的当且仅当它的根节点的度数为奇数。

那我们对于一个连通图，取出其任意一棵生成树，跑这个流程。最终如果树是合法的，那么这个图就是合法的（其它边都不选就行了），并且方案是可以直接构造的。如果最终树是非法的，那必然这个树仅存在一个偶度点（根节点）。考虑加入一条非树边或者删除一条树边，发现无论这个边怎么连怎么删，都必然不会改变偶度点个数的奇偶性（要么偶度点个数加二，要么减二，要么不变）。也就是说，如果树是非法的，那么无论你怎么改，那都不可能是合法的。这样说明了一个连通块合法当且仅当偶度点个数为偶数。

更进一步，由于任意一张图的奇度点个数必然为偶数，所以一个连通块合法当且仅当其大小为偶数。一个图合法当且仅当其所有连通块的大小都为偶数。

对于动态的情况，我们使用一种有趣的分治方法。由于答案是递减的，我们可以我们以时间作为分治的关键字，然后同时也维护值域的答案区间。具体操作大概是：

对于一次分治（时间 [l,r]，值域 [x,y]）

  1. 把 [l,r] 的时间区间中满足边的边权 w_i<x 的边全部加入并查集
  2. 取时间的中点 mid。我们把值域在 [x,y] 且时间在 [l,mid] 的边按值域从小到大加入并查集，直到合法。这相当于是使 mid 合法的最小答案 z。
  3. 由于答案是递减的，所以这个 z 是 [l,mid] 时间段的下界，且是 [mid+1,r] 时间段的上界。分别继续分治两个时间段即可。
  4. 在 2, 3（其中包括两次分治结束）后都要回到初始状态（即把这些操作全部都撤回掉）。

也有一种类似的整体二分做法，大概就是分治答案区间，去找最小合法时间，然后类似地递归下去。本质上没什么区别（因为答案和时间都是单调的），就不多赘述了。

复杂度：每一个分治区间的复杂度都是 (C\times(r-l)+C\times(y-x))\log n 的，即一层的复杂度为 O(m\log n)，总复杂度 O(m\log m\log n)。

分治有不少的细节。需要很注意。
还有别忘了离散化。这样分治在出现两个权值相同的边时可能会寄，需要在离散化时手动区分一下。

https://codeforces.com/contest/603/submission/167729346