一类以并查集在建树过程中维护各种信息的值——克鲁斯卡尔重构树前身

第一次见到是在zzu的校赛中，印象深刻。

H. Sum of Maximum Weights

题意

给定一棵树，求树上任意两点间最短路径中的最大边权的和。

官方 Solution

  1. 将边按权值排序，每次处理当前的最大权值。
  2. 处理每条边时，由于树的性质，边的起点和终点一定连通。设两个组 UU 和 VV，则 UU 组中任意成员到 VV 组中任意成员的最大路径边权必为当前边的权值 ee，故可以写出 ans+=siz[u]×siz[v]×eans += siz[u] \times siz[v] \times e。
  3. 将两组合并，重复上述过程，最终得到答案。

我的理解

如果了解克鲁斯卡尔重构树，这就是一道板子题。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e6 + 5;
const int M = N * 2;

int a[N], b[N];
int f[N], siz[N];

int Get(int u) {
    return u == f[u] ? u : f[u] = Get(f[u]);
}

struct edge {
    int u, v, e;
} e[N];

bool cmp(edge x, edge y) {
    return x.e < y.e;
}

signed main() {
    int n;
    cin >> n;
    for (int i = 1; i < n; i++) {
        scanf("%lld %lld %lld", &e[i].u, &e[i].v, &e[i].e);
    }
    for (int i = 1; i <= n; i++) {
        f[i] = i;
        siz[i] = 1;
    }
    sort(e + 1, e + n, cmp);
    int ans = 0;
    for (int i = 1; i < n; i++) {
        edge t = e[i];
        int u = t.u, v = t.v, e = t.e;
        u = Get(u), v = Get(v);
        if (siz[u] < siz[v]) swap(u, v);
        ans += siz[u] * siz[v] * e;
        f[u] = v;
        siz[v] += siz[u];
    }
    cout << ans << endl;
}

牛客小白月赛25C

题目链接

题意

树上有黑白点，可以将一个黑点改成白点，求修改后最大白色连通块。

Solution

  1. 对于白色连通块，用并查集维护连通性和 size。
  2. 暴力枚举黑色节点，累加其相邻的白色连通块大小，取最大值即为答案。
  3. Debug：注意字符串下标和数组下标混用的情况。特判全是白色节点的情况。
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
int n, m;
int a[N];
int col[N];

struct DSU {
    vector<int> f, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

vector<int> e[N];

void solve() {
    cin >> n;
    string s;
    cin >> s;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'W') col[i + 1] = 1;
        else col[i + 1] = 0;
    }
    DSU dsu(n + 1);
    for (int i = 1; i <= n - 1; i++) {
        int u, v;
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
        if (col[u] && col[v]) dsu.merge(u, v);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int sum = 0;
        if (col[i] == 0) {
            for (auto v : e[i]) {
                if (col[v] == 1) sum += dsu.siz[dsu.find(v)];
            }
            ans = max(ans, sum + 1);
        }
    }
    if (ans == 0) ans = n;
    cout << ans << endl;
}

2020牛客寒假算法基础集训营1 F

题目链接

题意

给定一棵树，每个顶点被染成白色或黑色。求取两个不同的点，它们的简单路径上有且仅有一个黑色点的取法有多少。

Solution

  1. 经过一个黑点的路径有两种：
    • 两个端点都是白点。
    • 其中一个端点是黑点。
  2. 预处理每个白点连通块上的白点个数。
  3. 设某黑点连接了 kk 个白点，第 ii 个白点的权值为 f(i)f(i)。
    • 第一种路径的数量为 ∑i=1k∑j=i+1kf(i)×f(j)\sum_{i=1}^k \sum_{j=i+1}^k f(i) \times f(j)，可以用前缀和优化。
    • 第二种路径的数量为 ∑i=1kf(i)\sum_{i=1}^k f(i)。

克鲁斯卡尔重构树板子题

题目链接

题意

给出一张普通无向图，多次查询。每次查询给出两个点，求连通两个点的所有路径中，每条路径都有最小边权值，求这些最小边权值中的最大值。

Solution

  1. 先跑最大生成树，树上路径最小值即为答案。
  2. 使用克鲁斯卡尔重构树，每次合并时开一个新点，新点的权值为当前边的权值。
  3. 查询时，找到两个点的 LCA，LCA 的权值即为答案。
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
int n, m;
int a[N];
vector<int> e[N];
int fa[N], son[N], dep[N], siz[N];
int top[N];

void dfs1(int u, int f) {
    fa[u] = f;
    siz[u] = 1;
    dep[u] = dep[f] + 1;
    for (int v : e[u]) {
        if (v == f) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    if (!son[u]) return;
    dfs2(son[u], t);
    for (int v : e[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

int lca(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

void add(int u, int v) {
    e[u].push_back(v);
}

struct edges {
    int u, v, w;
    bool operator<(const edges &tmp) {
        return w > tmp.w;
    }
};

edges edge[M];

void solve() {
    int q;
    cin >> n >> m;
    DSU dsu(2 * n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        edge[i] = {u, v, w};
    }
    sort(edge + 1, edge + 1 + m);
    int cnt = n;
    for (int i = 1; i <= m; i++) {
        auto [u, v, w] = edge[i];
        u = dsu.find(u), v = dsu.find(v);
        if (u != v) {
            cnt++;
            dsu.merge(cnt, u);
            dsu.merge(cnt, v);
            add(cnt, u);
            add(u, cnt);
            add(cnt, v);
            add(v, cnt);
            a[cnt] = w;
        }
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (dsu.find(i) == i) {
            dfs1(i, 0);
            dfs2(i, i);
        }
    }
    cin >> q;
    for (int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        if (dsu.find(u) != dsu.find(v)) {
            cout << -1 << endl;
            continue;
        }
        int mid = lca(u, v);
        cout << a[mid] << endl;
    }
}

相关题目

  1. BZOJ 3732：求图中连通两点路径中的最大边的最小值。
  2. BZOJ 3545。