「CF2222F」Building Tree

    「CF2222F」Building Tree

    CF2222F

    给出一个包含 nn 个点 mm 条边的无向图,边带权。

    对于任意路径,设其边权集合为 SS,则该路径的长度为 mex(S)\mathrm{mex}(S)。记 dis(u,v)\mathrm{dis}(u, v) 表示所有从 uu 到 vv 的路径中的最小路径长度。

    现在有 qq 个关键点 c1,…,cqc_1, \dots, c_q,连接 cu,cvc_u, c_v 的代价是 dis(cu,cv)\mathrm{dis}(c_u, c_v),求让这 qq 个关键点连通的最小代价总和。

    数据范围:1≤n,m≤3×1051 \leq n, m \leq 3 \times 10^5,1≤q≤n1 \leq q \leq n,0≤w≤m0 \leq w \leq m。

    时空限制:2.52.5s / 512512MiB。

    Solution

    考虑放宽限制,如果把权值为 xx 的所有边都删掉之后 u,vu, v 依然连通,那么可以认为新图中 u,vu, v 之间有一条权值为 xx 的边。由于求的是最小生成树,即使 xx 比真正的 dis(u,v)\mathrm{dis}(u, v) 更大也没有关系。

    发现这个形式与缺一分治比较像。

    考虑分治,设 solve(l,r)\mathrm{solve}(l, r) 表示当前加入了边权不属于 [l,r][l, r] 的所有边。

    • 向左侧递归时,加入边权属于 [mid+1,r][\mathrm{mid} + 1, r] 的所有边。
    • 向右侧递归时,加入边权属于 [l,mid][l, \mathrm{mid}] 的所有边。
    • 回溯时,将递归时加入的边撤销掉。

    这样,递归到叶子结点 [l,l][l, l] 时,相当于就是将权值为 ll 的所有边全都删掉了。

    但显然不能递归到叶子结点 [l,l][l, l] 的时候,再枚举任意两个点 u,vu, v 是否连通,尝试在新图中加边。

    所以我们得考虑在递归的过程中加边,注意到:向左侧递归,在加入边权属于 [mid+1,r][\mathrm{mid} + 1, r] 的所有边时,如果 u,vu, v 在此刻连通了,那么意味着把权值属于 [l,mid][l, \mathrm{mid}] 的所有边都删掉之后 u,vu, v 依然连通,于是我们可以认为新图中 u,vu, v 之间有一条权值为 ll 的边(向右侧递归也一样,只是在新图中加入一条边权为 mid+1\mathrm{mid} + 1 的边)。

    在原图上维护可撤销并查集(每个集合需要额外维护一个代表特殊点),在新图上维护普通并查集。如果递归的过程中,原图中 u,vu, v 在此刻连通了,设 u,vu, v 所在集合的代表特殊点分别为 p,qp, q,那么尝试在新图中连接 p,qp, q。

    时间复杂度 O(mlog⁡2m)\mathcal{O}(m \log^2 m)。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    const int N = 300100;
    
    int n, m, Q;
    
    std::vector<std::pair<int, int>> e[N];
    
    int flag[N];
    
    i64 ans;
    struct nDSU {
        std::vector<int> fa;
    
        void init(int n) {
            fa.resize(n + 1);
            std::iota(fa.begin(), fa.end(), 0);
        }
    
        int get(int x) {
            return fa[x] == x ? x : fa[x] = get(fa[x]);
        }
    
        bool merge(int x, int y, int z) {
            int p = get(x), q = get(y);
            if (p == q) {
                return 0;
            }
            ans += z;
            fa[p] = q;
            return 1;
        }
    } d1;
    
    // 可撤销并查集
    struct DSU {
        std::vector<int> sze, key;
        std::vector<int> fa;
        std::vector<std::array<int, 3>> his;
    
        DSU() {}
        DSU(int n) {
            init(n);
        }
    
        void init(int n) {
            sze.assign(n + 1, 1);
            key.assign(n + 1, 0);
            fa.resize(n + 1);
            std::iota(fa.begin(), fa.end(), 0);
            his.clear();
        }
    
        int get(int x) {
            return fa[x] == x ? x : get(fa[x]); // 按秩合并不能路径压缩
        }
    
        bool merge(int x, int y, int z) {
            int p = get(x), q = get(y);
            if (p == q) {
                return 0;
            }
            if (sze[p] > sze[q]) {
                std::swap(p, q);
            }
            his.push_back({p, q, key[q]});
            if (key[p] && key[q]) {
                d1.merge(key[p], key[q], z);
            }
            sze[q] += sze[p], key[q] = key[p] ? key[p] : key[q], fa[p] = q;
            return 1;
        }
    
        int time() {
            return his.size();
        }
        
        void revert(int tim) {
            while (his.size() > tim) {
                auto [p, q, k] = his.back(); his.pop_back();
                sze[q] -= sze[p], key[q] = k, fa[p] = p;
            }
        }
    } d0;
    
    void solve(int l, int r) {
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
    
        int tim = d0.time();
        for (int i = mid + 1; i <= r; i ++) {
            for (auto [x, y] : e[i]) {
                d0.merge(x, y, l);
            }
        }
        solve(l, mid);
    
        d0.revert(tim);
        for (int i = l; i <= mid; i ++) {
            for (auto [x, y] : e[i]) {
                d0.merge(x, y, mid + 1);
            }
        }
        solve(mid + 1, r);
    }
    
    void work() {
        std::cin >> n >> m >> Q;
    
        for (int i = 0; i <= m; i ++) {
            e[i].clear();
        }
        for (int i = 1; i <= m; i ++) {
            int x, y, z;
            std::cin >> x >> y >> z;
            e[z].push_back({x, y});
        }
    
        d0.init(n), d1.init(n), ans = 0;
        for (int i = 1; i <= n; i ++) {
            flag[i] = 0;
        }
        for (int i = 1; i <= Q; i ++) {
            int x;
            std::cin >> x;
            flag[x] = 1;
            d0.key[x] = x;
        }
    
        solve(0, m);
    
        int p = 0;
        for (int i = 1; i <= n; i ++) {
            if (flag[i]) {
                int x = d1.get(i);
                if (!p) {
                    p = x;
                } else if (x != p) {
                    std::cout << -1 << '\n';
                    return;
                }
            }
        }
    
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }
    
    /*
    1
    10 12 5
    8 2 0
    10 1 1
    6 10 0
    4 2 3
    4 3 2
    3 8 3
    10 7 0
    4 5 1
    6 4 0
    2 10 0
    1 3 0
    7 9 0
    6 1 7 9 5
    */