25D Roads not only in Berland 用并查集区分森林边与多余边，1245D Shichikuji and Power Grid 又把并查集放进 Kruskal。本文换一个角度：不再只问“两点是否连通”，而是比较一次合并之后还能立刻得到什么统计量。

三道题依次处理群组传播、语言翻译和带权树路径查询。第一题读取完全部关系后查询连通块大小；第二题从连通块数量推导最少新增关系，并单独处理“所有人都没有语言”的边界；第三题则按权值逐批加边，在每次合并时计算新出现的点对数。

1. 官方信息与训练顺序

以下题名、难度、标签和约束于 2026-09-17 通过 Codeforces 官方题目页与题库数据核对。

题目 难度 官方标签 关键约束 本文训练点
1167C · News Distribution 1400 dfs and similar、dsu、graphs n,m≤5×10^5，群组总人数不超过 5×10^5 用星形合并替代建群组完全图
277A · Learning Languages 1400 dfs and similar、dsu 2≤n,m≤100 连通块减一与全零特殊情况
1213G · Path Queries 1800 divide and conquer、dsu、graphs、sortings、trees n,m≤2×10^5，边权与询问值不超过 2×10^5 权值扫描与新增点对计数

建议按表中顺序练习。前两题先把自然语言关系压缩为连通块，第三题再让连通块随查询阈值增长。

2. 共同骨架：根节点代表一个集合

并查集为每个元素维护一个父节点。根节点代表整个集合，size[root] 保存集合大小。

  • find(x) 沿父指针找到根，并用路径压缩缩短后续查询；
  • unite(a,b) 先找两个根，若不同就把小集合挂到大集合；
  • 同一个集合内部再合并不会产生任何变化。

按大小合并与路径压缩结合后，单次操作的均摊复杂度是 O(α(n))。α 是反阿克曼函数，在竞赛数据范围内可视为极慢增长的常数，但证明和代码仍应保留这个准确写法。

容器 保存内容 只有根节点上的值才有意义吗
parent[x] x 当前指向的父节点 否
size[x] 以 x 为根的集合大小 是
题目答案 可能是最终块大小、块数或新增点对 视题目而定

3. 第一题：1167C News Distribution

3.1 为什么不能把每个群组建成完全图

一个群组中的任意两个人都可以直接传递消息。最直观的建图会给大小为 k 的群组加入 O(k²) 条边；当单个群组接近五十万人时，这个数量完全不可接受。

连通性不要求保留每一条直接关系。若群组成员为 a1,a2,…,ak，只需合并：

1
unite(a1, a2), unite(a1, a3), …, unite(a1, ak)

这 k−1 次合并已经让整组位于同一连通块。不同群组若共享成员，并查集还会自动把消息传播范围继续合并。

3.2 手工演算

设有群组 {2,5,4}、{1,2}、{6,7}，用户 3 不在任何群组中。

读入阶段 执行的合并 当前非平凡连通块
群组 {2,5,4} 2-5、2-4 {2,4,5}
群组 {1,2} 1-2 {1,2,4,5}
群组 {6,7} 6-7 {6,7}

最后每位用户的答案就是所在块的大小：4 4 1 4 4 2 2。

3.3 正确性证明

引理 1： 每个群组的星形合并与群组完全图产生相同的连通关系。

证明： 星形合并让每个成员都与首位成员连通，所以任意两名组员都能经过首位成员互达；完全图没有再增加新的连通块关系。∎

引理 2： 处理完所有群组后，两名用户位于同一并查集集合，当且仅当消息可以从其中一人传播到另一人。

证明： 每次合并都来自真实的共同群组，因此并查集不会连接无法传播的用户。反过来，一条传播链由若干共同群组关系组成，引理 1 保证链上的每一步都被合并，因此链两端最终同根。∎

定理： 对用户 i 输出 size[find(i)] 正好等于从 i 开始传播后知道消息的人数。

证明： 由引理 2，可收到消息的用户集合恰是 i 的连通块；根节点的 size 正是该块元素数。∎

3.4 完整 C++17 实现

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
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

class DSU {
public:
    explicit DSU(int n) : parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }

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

private:
    vector<int> parent;
    vector<int> size;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    DSU dsu(n);

    for (int group = 0; group < m; ++group) {
        int k;
        cin >> k;
        if (k == 0) continue;

        int first;
        cin >> first;
        for (int index = 1; index < k; ++index) {
            int member;
            cin >> member;
            dsu.unite(first, member);
        }
    }

    for (int user = 1; user <= n; ++user) {
        if (user > 1) cout << ' ';
        cout << dsu.componentSize(user);
    }
    cout << '\n';
    return 0;
}

时间复杂度为 O((n + Σk_i) α(n))，空间复杂度为 O(n)。空群组不能读取首位成员，这是最常见的输入错位来源。

4. 第二题：277A Learning Languages

4.1 把“会同一种语言”看成连接

若员工 u 和 v 会同一种语言，他们可以直接沟通。若 u 会英语、v 同时会英语和德语、w 会德语，那么 u 与 w 也能通过 v 间接沟通。

可以建立“员工—语言”二分图，也可以只在员工之间做并查集。对每种语言记录第一位使用者；后来遇到会该语言的员工时，把两人合并即可。

4.2 为什么通常是连通块数减一

假设当前有 c 个互不沟通的员工连通块，并且至少有人掌握一种语言。

  • 一次课程可以让某块中的一名员工学会另一块已有的语言，从而把两个块连接；
  • 一次课程最多让连通块数量减少 1；
  • 因而至少需要 c−1 次；
  • 选定一个已有语言的块作为中心，把其余每个块各接一次，恰好使用 c−1 次。

4.3 全员零语言为什么不是 c−1

若所有员工都不会任何语言，最开始根本没有一门可以作为桥梁的已有语言。即使给第一位员工上一门课，也只是创建了第一个语言使用者，没有合并两个已有块。

情况 第一门课程的作用 最少费用
至少一人已有语言 可以把另一个块接入已有网络 c−1
所有人都无语言 先创建共同语言的第一个使用者 n

全零时，让每个人都学习同一种语言需要 n 次，也显然足够。这个边界不能被普通的“块数减一”公式覆盖。

4.4 正确性证明

若至少存在一门已掌握语言，并查集连通块与当前可间接沟通的员工集合完全一致。一次付费课程至多合并两个块，所以 c−1 是下界；固定一个已有语言作为桥梁，逐块连接可达到该下界。

若无人掌握语言，每个人最终至少要掌握一门，否则他无法参与任何沟通，所以至少需要 n 次；让所有人学习同一种语言用 n 次完成，达到下界。

4.5 完整 C++17 实现

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
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;

class DSU {
public:
    explicit DSU(int n) : parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    void unite(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return;
        if (size[a] < size[b]) swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }

private:
    vector<int> parent;
    vector<int> size;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    DSU dsu(n);
    vector<int> firstSpeaker(m + 1, 0);
    bool anyoneKnowsLanguage = false;

    for (int employee = 1; employee <= n; ++employee) {
        int count;
        cin >> count;
        if (count > 0) anyoneKnowsLanguage = true;

        while (count--) {
            int language;
            cin >> language;
            if (firstSpeaker[language] == 0) {
                firstSpeaker[language] = employee;
            } else {
                dsu.unite(employee, firstSpeaker[language]);
            }
        }
    }

    if (!anyoneKnowsLanguage) {
        cout << n << '\n';
        return 0;
    }

    int components = 0;
    for (int employee = 1; employee <= n; ++employee) {
        if (dsu.find(employee) == employee) components++;
    }
    cout << components - 1 << '\n';
    return 0;
}

最多读取 n×m 个语言编号，时间复杂度为 O((n + Σk_i) α(n))，空间复杂度为 O(n+m)。

5. 第三题：1213G Path Queries

5.1 朴素方法为什么不够

每个询问给出阈值 q，要求统计多少对顶点的简单路径上最大边权不超过 q。

逐个询问遍历所有点对要处理 O(mn²) 个组合；即便每次只扫描整棵树，也会达到 O(mn)，在二十万规模下仍不可行。关键是把询问按阈值排序，让更大的阈值复用较小阈值已经开放的边。

5.2 阈值子图与唯一路径

只保留边权 ≤q 的边，得到一片森林。树中 u 到 v 的路径唯一，因此：

1
2
3
路径最大边权 ≤ q
⇔ 路径上的每条边都已被保留
⇔ u 与 v 在阈值子图中连通

问题于是变成：阈值逐渐增大、边逐渐加入时，当前森林内共有多少对连通顶点。

5.3 一次合并为什么新增 a×b 对

加入一条边，若它连接大小分别为 a 和 b 的两个分量：

  • 原来每个分量内部的点对已经统计；
  • 合并后新增的点对必须一端来自第一个分量、另一端来自第二个分量；
  • 选择两端共有 a×b 种。

这也能由组合数恒等式验证：

1
C(a+b, 2) − C(a, 2) − C(b, 2) = a×b

答案可能达到 C(200000,2)=19,999,900,000，必须使用 long long。

5.4 手工演算

考虑链 1—2—3—4，边权依次为 1、3、2。按权值排序后处理 1、2、3。

加入边权 被合并的分量大小 新增点对 累计点对
1 1 与 1 1 1
2 1 与 1 1 2
3 2 与 2 4 6

所以阈值 1、2、3 的答案分别是 1、2、6。第三步新增的四对跨越了中间权值为 3 的边。

5.5 正确性证明

不变量： 回答阈值 q 前，并查集中的集合恰好是由所有权值不超过 q 的边形成的连通块，累计值恰好是这些块内部的无序点对总数。

初始没有边，每个点单独成块，点对数为 0，不变量成立。加入一条合法边时，原图是树，所以边的两端当前属于不同分量；合并大小为 a,b 的块只新增跨块的 a×b 对，其他点对不变，因此不变量继续成立。

处理完所有权值 ≤q 的边后，阈值子图的连通块已经完整。由树上唯一路径性质，同块点对恰好是路径最大边权不超过 q 的点对，所以记录的累计值就是询问答案。∎

5.6 完整 C++17 实现

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
#include <algorithm>
#include <iostream>
#include <numeric>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

class DSU {
public:
    explicit DSU(int n) : parent(n + 1), size(n + 1, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    long long uniteAndCount(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b) return 0;
        if (size[a] < size[b]) swap(a, b);
        long long added = 1LL * size[a] * size[b];
        parent[b] = a;
        size[a] += size[b];
        return added;
    }

private:
    vector<int> parent;
    vector<int> size;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<tuple<int, int, int>> edges;
    edges.reserve(max(0, n - 1));
    for (int index = 0; index < n - 1; ++index) {
        int u, v, weight;
        cin >> u >> v >> weight;
        edges.emplace_back(weight, u, v);
    }
    sort(edges.begin(), edges.end());

    vector<pair<int, int>> queries(m);
    for (int index = 0; index < m; ++index) {
        cin >> queries[index].first;
        queries[index].second = index;
    }
    sort(queries.begin(), queries.end());

    DSU dsu(n);
    vector<long long> answer(m);
    long long connectedPairs = 0;
    size_t edgeIndex = 0;

    for (const auto& [limit, originalIndex] : queries) {
        while (edgeIndex < edges.size() && get<0>(edges[edgeIndex]) <= limit) {
            const auto [weight, u, v] = edges[edgeIndex];
            (void)weight;
            connectedPairs += dsu.uniteAndCount(u, v);
            edgeIndex++;
        }
        answer[originalIndex] = connectedPairs;
    }

    for (int index = 0; index < m; ++index) {
        if (index > 0) cout << ' ';
        cout << answer[index];
    }
    cout << '\n';
    return 0;
}

排序占 O(n log n + m log m)，并查集操作为 O((n+m)α(n))，总空间复杂度 O(n+m)。n=1 时没有边，所有询问答案自然为 0。

6. 三题到底在统计什么

题目 合并发生在何时 根上维护的信息 最终答案
1167C 读到同一群组成员 集合大小 每个人所在块大小
277A 两人共享已有语言 集合大小即可 块数减一，另判全零
1213G 边权不超过当前阈值 集合大小 每次增加 a×b 后的累计值

并查集本身只维护集合划分。真正决定题目难度的是：什么事件触发合并，合并前后的统计量如何变化，以及询问能否离线重排。

7. 边界与错误清单

错误 后果 修正
为大小为 k 的群组加入 k² 条边 1167C 超时或爆内存 只与群组首位成员做 k−1 次合并
k=0 时仍读取首位成员 后续输入整体错位 空群组直接继续
277A 无条件输出 components−1 全员零语言时少算 1 用布尔量记录是否存在已知语言
对每个询问重新初始化并查集 1213G 退化到 O(mn) 边和询问都排序，单向扫描
边权等于阈值时没有加入 漏掉合法路径 条件必须是 weight <= limit
用 int 保存点对数 二十万点时溢出 乘法和累计值都使用 long long
输出排序后的询问顺序 答案位置错误 保存原下标并回填

8. 如何继续练习

如果对基础合并仍不熟，可以先回看 25D 的生成森林与多余边；如果已经理解 1213G 的权值扫描，再读 1245D 的 Kruskal 建模，比较两者共同的“按边权加入”过程与不同的答案含义。

本文的三份代码由 tests/verify-dsu-three-article.cjs 从 Markdown 原文提取，以 C++17 无警告编译；验证器会用独立 BFS、员工—语言连通图和逐点对路径最大值进行随机对拍，并覆盖五十万人群组以及二十万点、答案超过 32 位整数的长链。