【CF603E】 Pastoral Oddities

CF 传送门：CF603E

整体二分 + 可撤销并查集。

（这个方法是个人认为较简单的，除外还有LCT 维护、线段树分治的做法。）

考场上苦想正解觉得自己写得出来的我真的太 naive 了

Solution

Part 1 每个点的度数均为奇数

不妨称度数为奇数的点为奇点，为偶数称偶点。

逐一考虑题目限制条件。显然先从“每个点为奇点”考虑，因为它相对特殊。

先扔出一个很重要的结论：一个连通图内所有点为奇点，等价于该连通图内有偶数个节点。证明如下：

• 必要性：考场上阿巴出“若某连通图内的每个点都为奇点，则该图中点数必定为奇数”。

  这个性质的证明不难，手玩小样例即可，形象地说，奇点必定是成双成对出现的，若想要一个偶点变为奇点，必须同时让另一个偶点变为奇点（或者重新构造出一个点）。自己画画图构造一下很容易就能得出。

• 充分性：对于一个有偶数个节点的连通图，我们可以在它任意一种形态的生成树上构造出“所有点为奇点”的局面。

  具体地，从底向上遍历每一个节点，如果这个节点儿子连上来的边数为偶数，就连上他与父亲的边，反之则不然。对于根节点，因为其子树内其他节点的度数之和为 奇数 x 奇数 = 奇数，而度数总和为偶数，所以根节点的度数也为奇数。

结合这个结论和其充分性证明中的构造方式，可以发现：对于一个连通图，只要添上某一条边之后，它的点数变为偶数，那这条边就是这个边集中的最大边权。进一步地，想要把这个图真真切切构造成一个“所有点都为奇点”的情况，需要在图中删边，但是删的边一定不会是这条最大权的边。

由此，明白：既然我们只是要求“最小化边集中的最大边权”，那这个连通图内部如何删边我们其实毫不关心，只需要明白有这个操作，但是代码实现中无需写出，要想找到“最小化边集中的最大边权”，只需要看在加入哪条边之后总点数变为偶数即可。直白地说，对合法的边，能加就加。

Part 2 最小化边集中的最大边权

然后来考虑“最小化边集中的最大边权”这个限制条件。条件反射肯定就想到二分答案的做法，但是本题是动态加边，复杂度不允许每次加边后都来一次二分，故引导我们去考虑整体二分的做法。进一步地，为了保证能够使用整体二分，考虑证明最终答案的单调性。这个通过观察样例输出简单思考发现答案一定是单调不下降的。

按照整体二分的套路来，函数 solve(ql, qr, vl, vr) 表示现在处理在 /([ql,qr]/) 之间的询问，且它们的答案都是边按照权值从小到大排序之后，位于 /([vl,vr]/) 之中的某边的边权。（使用 /(e/) 数组按输入顺序存放边，/(b/) 数组按权值从小到大存放边。）

按照之前的推论，我们根本不关心连通块内部怎么删边，故要先确保在 /(e/) 中编号小于 /(ql/)、/(w/) 中编号小于 /(vl/) 的边都先加入。为了继续二分处理询问，设 /(mid=/frac{vl+vr}{2}/)，我们就需要求出在询问 /([ql,qr]/)，中，哪个询问的答案是 /(b_{mid}.w/)，记此答案为 /(Ans/)。若求出了 /(Ans/)，那么接下来要递归的两个函数的分别是 solve(ql, Ans - 1, mid + 1, vr) 和 solve(Ans, qr, vl, mid)，即分别递归左子区间和右子区间。

Part 3 加边

再回过头考虑加边细节：

1. 为求解 /(Ans/) 加边：我们首先肯定要保证 /(e/) 中编号小于 /(ql/) 的边且 /(w/) 中编号小于 /(mid/) 的边都必须得加入，这是根据能加就加的原则。然后再从 /(e_{ql}/) 遍历到 /(e_{qr}/)，依次加入这些边，直到加入某条边之后整个图中没有一个内部点数为奇数的连通块，则这条边就是 /(Ans/)。
2. 为递归 solve(ql, Ans - 1, mid + 1, vr) 加边：显然，为了不妨碍下一个递归函数，我们只需要在递归这个函数之前加入 /(e/) 中编号小于 /(ql/) 的边且 /(w/) 中编号小于 /(mid/) 的边。
3. 为递归 solve(Ans, qr, vl, mid) 加边：同理，此时要先加入 /(e/) 中编号在 /([ql, Ans)/) 的边且其边权小于 /(b_{vl}.w/) 的边。

综上，我们可以发现：

1. 我们想维护连通块内的节点数；
2. 每次递归函数中，上述三个加边步骤有所重复（比如第一步的前半部分和第二步）；
3. 我们想尽可能节省空间。

这三条（或者更多）指向了我们维护这些边、连通块所使用的工具：可撤销并查集。

为什么要“可撤销”？发现第一步加边之后，要想执行第二步加边操作，只需要撤销掉第一步后半部分的加边操作即可，无需重新加边（显然，撤销比初始化再重新加边要方便的多）。

嗯，然后这道题就结束了。

简单提一嘴可撤销并查集，它其实就是在并查集的基础上，不路径压缩，然后再开个栈存放每次合并的两个根节点，便于撤销即可。

Code

#include<bits/stdc++.h>
using namespace std;
 
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
const int maxn = 3e5 + 5;
int n, m, num;
int fa[maxn], sz[maxn], stk[maxn], tot, ans[maxn];
struct node{
    int u, v, w, id;
}e[maxn], b[maxn];
bool operator <(const node &a, const node &b){
    return a.w < b.w;
}
 
inline int fnd(int x){
    return x == fa[x] ? x : fnd(fa[x]);
}
 
inline void erase(int lmt){
    while(tot > lmt){
        int v = stk[tot--], u = fa[v];
        fa[v] = v, sz[u] -= sz[v];
        if((sz[u] & 1) and (sz[v] & 1)) num += 2; 
    }
}
 
inline void merge(int x, int y){
    x = fnd(x), y = fnd(y);
    if(x == y) return;
    if(sz[x] < sz[y]) swap(x, y);
    if((sz[x] & 1) and (sz[y] & 1)) num -= 2;
    sz[x] += sz[y], fa[y] = x, stk[++tot] = y;
}
 
inline void slv(int ql, int qr, int vl, int vr){
    if(ql > qr or vr < vl) return;
    if(vl == vr){
        rep(i, ql, qr) ans[i] = b[vl].w; return;
    } int mid = vl + vr >> 1, nw = tot;
    rep(i, vl, mid) if(b[i].id < ql) merge(b[i].u, b[i].v);//加入之前的边 
    int Ans = qr + 1, nw2 = tot;
    rep(i, ql, qr){
        if(e[i].w <= b[mid].w) merge(e[i].u, e[i].v);
        if(!num){Ans = i; break;}//找到 ans[mid] 
    } erase(nw2), slv(ql, Ans - 1, mid + 1, vr), erase(nw);//递归左子区间 
    rep(i, ql, Ans - 1) if(e[i].w <= b[vl].w) merge(e[i].u, e[i].v);//添加满足限制的边 
    slv(Ans, qr, vl, mid), erase(nw); //递归右子区间 
} 
 
int main(){
    scanf("%d%d", &n, &m), num = n;
    rep(i, 1, n) sz[i] = 1, fa[i] = i;
    rep(i, 1, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), e[i].id = i, b[i] = e[i];
    sort(b + 1, b + m + 1), b[m + 1].w = -1;
    slv(1, m, 1, m + 1); rep(i, 1, m) printf("%d/n", ans[i]);
    return 0;
}

感谢阅读。