「CF2222F」Building Tree

发表于 分类于 本文字数： 1.3k 阅读时长 ≈ 1 分钟

Description

Link：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)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
#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
*/