困难分治题

starish · 2026-11-10 21:30:31 · 题解

怎么没人写题解，我来写一发！

题意

有一个无向连通图，每条边有权值 W_i 和颜色 C_i，求最小生成树；Q 次加边，每次加边后重新确定最小生成树；给定 K 个点对，令 P_i 为最小生成树上 A_i 到 B_i 路径的颜色异或和，求所有非空子集异或和的最大值。(Q \le 10^5,\ N,M,K \le 2\times 10^5,\ W_i,C_i<2^{30})

题解

先考虑路径异或的转化。这是一个经典问题：先加入 K 条颜色为 0 的虚边 (A_i,B_i)，再加入树边；每次加边如果成环，就把 d_u\oplus d_v\oplus c 加入线性基，其中 d_u 是 u 到并查集根的路径异或和。

实现时维护两个独立并查集：

把所有边离线做时间轴分治，叶子从左到右处理，处理到叶子时前一条边已经解密。

考虑区间 [l,r]，进入时对应时刻 l。候选集 E 是在时刻 l 已存在、权值和颜色已知、可能入选的边。未来边是编号在 [l+1,r] 的边。

第一轮：把编号在 [l+1,r] 的未来边的两个端点临时合并到 A 中，只用端点，然后按 (W_i,i) 顺序把 E 中能合并的边记为 F。F 是在整个区间内 Kruskal 必选的边：即使所有未来边和所有优先于它的候选边都已加入，它两端仍不连通，所以在区间内任何时刻都必选。撤销临时合并，把 F 同时加入 A 和 B，永久保留到当前分治节点的后代。

第二轮：在已加入 F 的基础上，不加入未来边，只对 E\setminus F 做一次 Kruskal，能加入的保留为 E'，其余永久丢弃。被丢弃的边在当前图中已经有一条由更优先边组成的路径连接其端点；以后只会继续加边，这条路径不会消失，所以它在之后任何时刻也不可能被 Kruskal 选中。撤销第二轮试选合并，只保留 F。

令 mid=\left\lfloor\frac{l+r}{2}\right\rfloor 先递归左半区间 [l,mid]，候选集为 E'。左半区间处理完后，编号在 [l+1,mid+1] 的边都已经完成解密，把它们加入 E'，再递归右半区间 [mid+1,r]。

叶子 l=r 时，对剩余候选边做 Kruskal，每条成功选中的真实边同时加入 B；查询线性基最大异或并输出。若还有下一条边，就用当前答案立即解密编号为 l+1 的边。

复杂度：设当前区间未来边数为 d=r-l，进入时 A 有 c 个连通块，临时合并未来边后变为 c'，则 c-c'\le d 第一轮选出 c'-1 条必选边，收缩后第二轮只会留下 (c-1)-(c'-1)=c-c'\le d 条候选边。因此除根节点需要处理 M 条初始边外，每层分治处理的候选边和未来边总数均为 O(Q)。总复杂度双 \log 的。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10;
struct Dsu1{
    int f[N], sz[N];
    stack<pair<int, int> > stk;
    void init(int n) {for (int i = 1; i <= n; i++) f[i] = i, sz[i] = 1;}
    int find(int u) {while (f[u] != u) u = f[u]; return u;}
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return 0;
        if (sz[u] < sz[v]) swap(u, v);
        stk.push({u, v});
        f[v] = u;
        sz[u] += sz[v];
        return 1;
    }
    void pop(int x) {
        while ((int)stk.size() > x) {
            auto [u, v] = stk.top();
            sz[u] -= sz[v];
            f[v] = v;
            stk.pop();
        }
    }
}D1;
struct Bs{
    int bs[31];
    stack<int> stk;
    void insert(int x) {
        for (int i = 30; i >= 0; i--) {
            if (!((x >> i) & 1)) continue;
            if (!bs[i]) {stk.push(i); bs[i] = x; return ;};
            x ^= bs[i];
        }
    }
    int query() {
        int res = 0;
        for (int i = 30; i >= 0; i--) res = max(res, res ^ bs[i]);
        return res;
    }
    void pop(int x) {
        while ((int)stk.size() > x) {
            bs[stk.top()] = 0;
            stk.pop();
        }
    }
};
struct Dsu2{
    int f[N], sz[N], w[N];
    Bs b;
    stack<tuple<int, int, int> > stk;
    void init(int n) {for (int i = 1; i <= n; i++) f[i] = i, sz[i] = 1, w[i] = 0;}
    int find(int u, int &res) {while (f[u] != u) res ^= w[u], u = f[u]; return u;}
    bool merge(int u, int v, int c) {
        int resu = 0, resv = 0;
        u = find(u, resu), v = find(v, resv);
        if (u == v) {
            stk.push({-1, -1, (int)b.stk.size()});
            b.insert(resu ^ resv ^ c);
            return 0;
        }
        if (sz[u] < sz[v]) swap(u, v), swap(resu, resv);
        stk.push({u, v, resv});
        f[v] = u;
        sz[u] += sz[v];
        w[v] = resu ^ resv ^ c;
        return 1;
    }
    void pop(int x) {
        while ((int)stk.size() > x) {
            auto [u, v, resv] = stk.top();
            stk.pop();
            if (u == -1) {
                b.pop(resv);
                continue;
            }
            sz[u] -= sz[v];
            f[v] = v;
            w[v] = resv;
        }
    }
}D2;
struct Edge{
    int u, v, w, c;
    void decode(int x) {
        int a = (1ll * x * 987654321 + 123456789) % (1 << 30);
        w ^= a, c ^= a;
    }
}E[N];
int n, m, k, q;
void solve(int l, int r, vector<int>& chs) {
    sort(chs.begin(), chs.end(), [&](int a, int b) {
        if (E[a].w != E[b].w) return E[a].w < E[b].w;   
        else return a < b;
    });
    pair<int, int> t1 = {D1.stk.size(), D2.stk.size()};
    if (l == r) {
        for (auto i : chs) if (D1.merge(E[i].u, E[i].v)) {
            D2.merge(E[i].u, E[i].v, E[i].c);
        }
        int ans = D2.b.query();
        cout << ans << '\n';
        if (l < m + q) E[l + 1].decode(ans);
    } else {
        for (int i = l + 1; i <= r; i++) D1.merge(E[i].u, E[i].v);
        vector<int> must, other;
        for (auto i : chs) {
            if (D1.merge(E[i].u, E[i].v)) must.push_back(i);
            else other.push_back(i);
        }
        D1.pop(t1.first), D2.pop(t1.second);
        for (auto i : must) D1.merge(E[i].u, E[i].v), D2.merge(E[i].u, E[i].v, E[i].c);
        pair<int, int> t2 = {D1.stk.size(), D2.stk.size()};
        vector<int> pd;
        for (auto i : other) if (D1.merge(E[i].u, E[i].v)) pd.push_back(i);
        D1.pop(t2.first), D2.pop(t2.second);
        int mid = (l + r) / 2;
        solve(l, mid, pd);
        for (int i = l + 1; i <= mid + 1; i++) pd.push_back(i);
        solve(mid + 1, r, pd);
    }
    D1.pop(t1.first), D2.pop(t1.second);
}
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        cin >> E[i].u >> E[i].v >> E[i].w >> E[i].c;
    }
    D1.init(n), D2.init(n);
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        D2.merge(u, v, 0);
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> E[m + i].u >> E[m + i].v >> E[m + i].w >> E[m + i].c;
    }
    vector<int> chs;
    for (int i = 1; i <= m; i++) chs.push_back(i);
    solve(m, m + q, chs);
    return 0;   
}