CF603E Pastoral Oddities

题意

给定一张 \(n\) 个点的无向图，初始没有边。

依次加入 \(m\) 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。

若存在，则还需要最小化边集中的最大边权。

题解

感觉自己找性质的能力还是太弱了。
首先有一个结论，如果整张图的联通块大小都为偶数，则一定有解。

证明:
1.若图中有大小为奇数的连通块，由于每条边会贡献 \(2\) 的度数，则每个点的度数之和一定为偶数，而由于图中每个点都为奇数，点数也为奇数，则总度数为奇数，矛盾了，所以无解。
2.若图中所有的连通块大小为偶数，从图中拉出一个生成树，从叶子开始，如果当前点的儿子个数为偶数个，则加上与父亲的边，这样除了根节点的度数都是奇数，而总度数为偶数，则根节点显然度数为奇数。

然后在看看限制条件，我们要让图中最大的边最小，一般除了二分之外一个比较常见的思路是最小生成树。
对于单次询问，我们可以将所有边排序，合并之后看看所有联通块大小是否为偶数，若不是则误解，否则就是最后一条边的权值。
我们仔细思考一下这个过程，直接正着做，对于一条边所连接的两个联通块可能会被后边加入的边给顶替，这似乎不是很好做。
但是有一个性质，对于一条边在某个时刻被使用到了，则显然的是从这条边出现时刻到当前时刻都会用到这条边。
我们将被使用看做出现，被顶替看做消失，其实就可以想到线段树分治，这样我们就可以配合可撤销并查集来判断答案。
但一条边被顶替的时间其实并不好求，我们尝试时间倒流，从后往前分治。
因为我们如果知道了最终状态中使用了哪些边，我们就能够确定一部分边的覆盖时间。
我们考虑在排序后的数组上面搞事情，我们在分治时设置一个指针指向排序后的数组。
若在根节点中图不满足条件，则指针向后移动，加入的时间就是它使用的最后一个时间。
不难发现这是一个边搜索边加边的线段树分治，但是由于线段树的结构所限，为了防止出现加在上面已经经过的节点上，右端点应该 \(-1\)。
最后的时间复杂度为 \(O(mlognlogm)\)。 code ;