Visits: 278

CF603E Pastoral Oddities

题意

• 给定一张 $n$ 个点的无向图，初始没有边。
• 依次加入 $m$ 条带权的边，每次加入后询问是否存在一个边集，满足每个点的度数均为奇数。
• 若存在，则还需要最小化边集中的最大边权。
• $n \le 10^5$，$m \le 3 \times 10^5$。

题解

对于一个 $n$ 个点的连通块，存在满足条件的边集的充要条件为 $n$ 是偶数，因为若 $n$ 是奇数，由于每个点的度数都是奇数，因此总度数为奇数，但由于每条边会产生的度数为 $2$，因此矛盾。

那如果 $n$ 为偶数，是否意味着一定存在呢？答案显然是肯定的，我们可以找出来一个生成树，然后从叶子开始，一个点与其父亲的连边保留当且仅当这个点与其所有儿子的连边数为偶数，那么就可以构造出来了。

因此这张图存在满足条件的边集当且仅当每个连通块的点数均为偶数。

我们接下来再考虑，对于一张给定的静态图，如何最小化边集中的最大边权呢？

考虑 kruskal 算法，由于加入边不会使答案变劣，因此用并查集维护每个连通块的点数，直到加入某条边后，满足所有连通块的点数均为偶数，这条边的边权就是答案。

扩展到动态加边，我们采用 LCT 维护每个连通块的最小生成树结构及大小，同时用大根堆维护所有在森林中的边。

每当我们加入一条边后，我们不断地尝试删除当前森林中边权最大的边，直到删除了某条边后出现了奇数大小的连通块，那么这条边的边权就是答案。

由于我们需要知道当前是否存在奇数大小的连通块，这里的 LCT 需要采用维护子树信息的技巧，即额外维护一个虚子树的信息总和，在 $\operatorname{access}$ 和 $\operatorname{link}$ 的时候更新。

显然每条边最多被删掉一次，因此在 $n,m$ 同阶的情况下，总时间复杂度为 $\mathcal O(n \log n)$。

代码

const int N = 4e5 + 7, M = 3e5 + 7;
int n, m, x[M], y[M], z[M], v[M], cnt;
pq<pair<int, int>> q;

struct LCT {
    int f[N], ch[N][2], s[N], v[N], a[N], c[N], d[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define get(p) (p == ch[f[p]][1])
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    #define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
    inline void upd(int p) {
        s[p] = s[ch[p][0]] + s[ch[p][1]] + d[p] + (p <= n);
        int o = a[c[lc]] > a[c[rc]] ? c[lc] : c[rc];
        c[p] = a[o] > a[p] ? o : p;
    }
    inline void spd(int p) {
        if (p && v[p]) {
            if (lc) rev(lc);
            if (rc) rev(rc);
            v[p] = 0;
        }
    }
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y) && !o) ch[y][v] = p;
    }
    void pre(int p) {
        if (!isrt(p)) pre(f[p]);
        spd(p);
    }
    inline void splay(int p) {
        pre(p);
        for (int x = f[p]; x = f[p], !isrt(p); rot(p))
            if (!isrt(x)) rot(get(p) == get(x) ? x : p);
    }
    inline void access(int p) {
        for (int x = 0; p; p = f[x=p])
            splay(p), d[p] += s[rc], d[p] -= s[rc=x], upd(p);
    }
    inline void mkrt(int p) {
        access(p), splay(p), rev(p);
    }
    inline void split(int x, int y) {
        mkrt(x), access(y), splay(y);
    }
    inline int fdrt(int p) {
        access(p), splay(p);
        while (lc) spd(p), p = lc;
        return splay(p), p;
    }
    inline void link(int x, int y) {
        mkrt(x), access(y), splay(y), cnt -= s[x] & 1, cnt -= s[y] & 1;
        d[f[x]=y] += s[x], upd(y), cnt += s[y] & 1;
    }
    inline void cut(int x, int y) {
        split(x, y), cnt -= s[y] & 1;
        f[x] = ch[y][0] = 0, upd(y), cnt += s[x] & 1, cnt += s[y] & 1;
    }
    inline int add(int i) {
        int x = ::x[i], y = ::y[i], z = ::z[i];
        bool ok = 1;
        if (fdrt(x) == fdrt(y)) {
            split(x, y);
            int o = c[y];
            if (a[o] > z) cut(::x[o-n], o), cut(::y[o-n], o), v[o] = 1;
            else ok = 0;
        }
        if (ok) {
            s[i+n] = 1, a[i+n] = z, c[i+n] = i + n;
            link(x, i + n), link(y, i + n), q.push(mp(z, i));
        }
        if (cnt) return -1;
        while (q.size()) {
            int o = q.top().se;
            q.pop();
            if (::v[o]) continue;
            cut(::x[o], o + n), cut(::y[o], o + n);
            if (cnt) {
                link(::x[o], o + n), link(::y[o], o + n);
                return q.push(mp(::z[o], o)), ::z[o];
            }
        }
        return 0;
    }
} lct;

int main() {
    rd(n), rd(m), cnt = n;
    for (int i = 1; i <= n; i++) lct.s[i] = 1, lct.c[i] = i;
    for (int i = 1; i <= m; i++)
        rd(x[i]), rd(y[i]), rd(z[i]), print(lct.add(i));
    return 0;
}