All men are brothers - 题解

标签与难度

标签: 并查集, 组合数学, 计数问题, 动态维护, 数据结构难度: 1900

题目大意喵~

你好呀，指挥官！Amy小姐姐又来出题考验我们啦，这次可不能被难倒喵~

题目是这样的：一开始有 $n$ 个素不相识的人。接下来会发生 $m$ 件事，每一件事都是两个人 $u$ 和 $v$ 成为了朋友。

这个“朋友关系”很特别哦，它有两个性质：

相互性: 如果 A 是 B 的朋友，那 B 也是 A 的朋友，喵~
传递性: 如果 A 是 B 的朋友，B 是 C 的朋友，那么 A 和 C 也会自动成为朋友！

这种关系会把所有 $n$ 个人划分成一个个“朋友圈”。在同一个朋友圈里，任何两个人都是朋友。不同朋友圈的人则互相不认识。

我们的任务是，在游戏最开始时，以及每当有一对新朋友产生后，都要计算出：从所有人中选出 4 个人，并且这 4 个人两两之间都不是朋友，一共有多少种选法呢？

解题思路分析

喵哈哈，这个问题看起来有点复杂，但只要我们把它拆解开来，就会发现其中的奥秘啦！

Step 1: 朋友关系的模型化，喵！

首先，我们来分析一下这个“朋友关系”。它满足相互性（对称性）和传递性。这不就是数学中的等价关系嘛！等价关系会将一个集合划分成若干个不相交的子集，每个子集我们称之为一个等价类。

在这个问题里，每个“朋友圈”就是一个等价类。在同一个朋友圈里的人，彼此都是朋友。我们的任务就是要从 $n$ 个人中选出 4 个，要求他们来自 4 个不同的朋友圈。

为了维护这些朋友圈（集合）的合并，最适合的工具就是并查集 (Disjoint Set Union, DSU) 啦！我们可以用并查集来追踪谁和谁在同一个朋友圈里，并且记录下每个朋友圈的大小。

parent[i]: 记录第 i 个人的“代表”（朋友圈的根节点）。
size[i]: 如果 i 是一个根节点，size[i] 就记录了这个朋友圈的总人数。

Step 2: 思考如何计数，呐~

我们的目标是：从所有朋友圈中，选出 4 个不同的朋友圈，然后从这 4 个朋友圈里各选一个人。

假设当前有 $k$ 个朋友圈，它们的大小分别是 $s_1, s_2, \dots, s_k$ 。如果我们想选出 4 个人，分别来自第 $i, j, l, p$ 这四个不同的朋友圈，那么选法就有 $s_i \times s_j \times s_l \times s_p$ 种。所以，总的方案数就是把所有四个不同朋友圈组合的乘积加起来：

\text{总方案数} = \sum_{1 \le i < j < l < p \le k} s_i s_j s_l s_p

这个公式直接计算起来太麻烦了，特别是每次朋友圈合并后，大小 $s_i$ 都会变化，重新计算会非常慢。我们得想个更聪明的办法，喵！

Step 3: 增量更新的魔法！

我们不从头计算，而是思考每次合并对答案有什么影响。

最开始，大家互不相识，有 $n$ 个朋友圈，每个圈里只有 1 个人。选 4 个来自不同圈的人，就等于从 $n$ 个人里随便选 4 个，方案数是 $C(n, 4)$ 。这就是我们的初始答案。

现在，假设我们要合并两个朋友圈，设为圈 $X$ 和圈 $Y$ ，它们的大小分别是 $s_x$ 和 $s_y$ 。这次合并，会让一些原本合法的“四人组”变得不合法。哪些四人组会失效呢？

一个四人组 {a, b, c, d} 原本是合法的，意味着 a, b, c, d 来自四个不同的朋友圈。如果它在合并后变得不合法，那一定是其中有两个人因为合并而成为了朋友。这只有一种可能：这四个人中，恰好有一个人来自圈 $X$ ，一个人来自圈 $Y$ ！

比如说，a 来自圈 $X$ ，b 来自圈 $Y$ ，c 来自圈 $Z$ ，d 来自圈 $W$ (其中 $X, Y, Z, W$ 互不相同)。合并前，这四个人两两不是朋友，是合法的。合并后，圈 $X$ 和圈 $Y$ 合并了，a 和 b 成了朋友，这个四人组就不合法了。

所以，答案的减少量，就等于这种失效的四人组的数量。我们来数一数：

从圈 $X$ 中选一个人：有 $s_x$ 种选法。
从圈 $Y$ 中选一个人：有 $s_y$ 种选法。
从剩下的所有人中选两个人（设为 c 和 d），并且 c 和 d 互相不是朋友。

第 3 步是关键。怎么计算呢？我们可以用容斥原理（或者叫补集思想）： (从剩下的人里选两个不是朋友的) = (从剩下的人里随便选两个) - (从剩下的人里选两个是朋友的)

剩下的人数是 $N' = n - s_x - s_y$ 。
从这 $N'$ 个人里随便选两个，有 $C(N', 2)$ 种方法。
从这 $N'$ 个人里选两个是朋友的，意味着这两个人必须来自同一个朋友圈（当然这个朋友圈不能是 $X$ 或 $Y$ ）。这个数量等于 $\sum_{k \neq X, Y} C(s_k, 2)$ 。

所以，每次合并， $X$ 和 $Y$ 两个圈时，答案的减少量为：

\Delta_{\text{ans}} = s_x \times s_y \times \left( C(n - s_x - s_y, 2) - \sum_{k \neq X, Y} C(s_k, 2) \right)

这个 $\sum_{k \neq X, Y} C(s_k, 2)$ 还是有点麻烦。但我们可以维护一个全局变量，就叫 pairs_in_same_set 吧，它表示当前所有“朋友对”的总数，即 $\sum_{\text{所有圈 } i} C(s_i, 2)$ 。那么， $\sum_{k \neq X, Y} C(s_k, 2)$ 就等于 pairs_in_same_set - $C(s_x, 2) - C(s_y, 2)$ 。

这样我们的思路就完整了！

初始化:
- 总答案 total_ways = $C(n, 4)$ 。
- pairs_in_same_set = 0 (因为初始每个圈只有1人， $C(1,2)=0$ )。
- 并查集初始化，n 个圈，每个大小为 1。
每次合并操作 (u, v):
- 用并查集找到 u 和 v 所在的圈的根节点 root_u 和 root_v。
- 如果 root_u == root_v，他们早就是朋友了，什么都不用做，答案不变。
- 如果 root_u != root_v，设它们的大小为 $s_u$ 和 $s_v$ 。 a. 计算答案减少量： - removable_pairs = pairs_in_same_set - C(s_u, 2) - C(s_v, 2)。 - other_people_count = n - s_u - s_v。 - ways_to_pick_two_others = C(other_people_count, 2) - removable_pairs。 - delta_ways = s_u * s_v * ways_to_pick_two_others。 b. 更新总答案：total_ways -= delta_ways。 c. 更新 pairs_in_same_set： - pairs_in_same_set -= C(s_u, 2) - pairs_in_same_set -= C(s_v, 2) - pairs_in_same_set += C(s_u + s_v, 2) d. 用并查集执行合并，更新圈的大小。
输出: 每次操作后，输出当前的 total_ways。

这样，我们每次只需要做一些常数时间的计算，就能动态地维护答案了，是不是很高效呀，喵~

代码实现

下面就是我根据这个思路精心编写的代码啦，加了详细的注释，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>

// 使用 long long 来防止计算过程中溢出，这很重要哦！
using ll = long long;

// 并查集结构体，把相关的数据和操作封装在一起，更清晰喵
struct DSU {
    std::vector<int> parent;
    std::vector<ll> sz; // 每个集合的大小

    // 初始化n个独立的集合
    DSU(int n) {
        parent.resize(n + 1);
        // std::iota 可以快速填充 0, 1, 2, ...
        std::iota(parent.begin(), parent.end(), 0);
        sz.assign(n + 1, 1);
    }

    // 查找x所属集合的根节点（带路径压缩）
    int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    // 合并x和y所在的集合（按大小合并）
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 总是把小的集合合并到大的集合里，可以优化树的高度
            if (sz[rootX] < sz[rootY]) {
                std::swap(rootX, rootY);
            }
            parent[rootY] = rootX;
            sz[rootX] += sz[rootY];
        }
    }
};

// 计算组合数 C(n, k) 的函数
ll combinations(ll n, int k) {
    if (k < 0 || k > n) {
        return 0;
    }
    if (k == 0 || k == n) {
        return 1;
    }
    if (k > n / 2) {
        k = n - k;
    }
    ll res = 1;
    for (ll i = 1; i <= k; ++i) {
        res = res * (n - i + 1) / i;
    }
    return res;
}

int main() {
    // 加速输入输出，让程序跑得更快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m;
    std::cin >> n >> m;

    DSU dsu(n);

    // total_ways: 最终答案，即选4个互不为朋友的人的方案数
    ll total_ways = combinations(n, 4);

    // pairs_in_same_set: 从同一个朋友圈里选2个人的总方案数
    // 即 Sum(C(size_i, 2)) for all sets i
    ll pairs_in_same_set = 0;

    // 输出初始答案
    std::cout << total_ways << "\n";

    for (int i = 0; i < m; ++i) {
        int u, v;
        std::cin >> u >> v;

        int root_u = dsu.find(u);
        int root_v = dsu.find(v);

        if (root_u != root_v) {
            ll size_u = dsu.sz[root_u];
            ll size_v = dsu.sz[root_v];

            // 1. 计算答案减少量
            // a. 先从 pairs_in_same_set 中移除旧的 u 和 v 所在集合的贡献
            ll pairs_in_other_sets = pairs_in_same_set - combinations(size_u, 2) - combinations(size_v, 2);
            
            // b. 剩下的人数
            ll other_people_count = n - size_u - size_v;

            // c. 从剩下的人中选2个互不为朋友的人的方案数
            ll ways_to_pick_two_others = combinations(other_people_count, 2) - pairs_in_other_sets;

            // d. 总的减少量
            ll delta_ways = size_u * size_v * ways_to_pick_two_others;
            
            total_ways -= delta_ways;

            // 2. 更新 pairs_in_same_set
            // 减去旧的贡献，加上新集合的贡献
            pairs_in_same_set -= combinations(size_u, 2);
            pairs_in_same_set -= combinations(size_v, 2);
            pairs_in_same_set += combinations(size_u + size_v, 2);

            // 3. 执行并查集合并
            dsu.unite(u, v);
        }

        // 每次操作后都输出当前答案
        std::cout << total_ways << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O(m \cdot \alpha(n))$
- 我们需要处理 $m$ 次合并操作。
- 每次操作中，并查集的 find 和 unite 操作的平均时间复杂度是近乎常数的，记为 $\alpha(n)$ （阿克曼函数的反函数），它增长得非常非常慢，对于所有实际情况都可以看作是一个小于 5 的小常数。
- 其他计算都是 $O(1)$ 的。
- 所以总的时间复杂度就是 $O(m \cdot \alpha(n))$ ，非常高效！
空间复杂度: $O(n)$
- 我们需要两个大小为 $n$ 的数组来维护并查集的 parent 和 sz 信息。所以空间开销是线性的，喵~

知识点总结

这道题真是一次有趣的挑战呢！它融合了好几个知识点：

并查集 (DSU): 识别出题目中的“传递性朋友关系”是等价关系，并使用并查集来高效地维护集合的合并与查询，是解题的第一步。
组合数学: 问题的核心是计数，需要用到组合数 $C(n, k)$ 的计算。
动态维护/增量思想: 面对一系列更新操作，直接重新计算整个答案通常是不可行的。本题的精髓在于思考每次“合并”操作对最终答案产生了多大的“变化量”（减少了多少），然后动态地更新答案。这种增量思想在许多算法竞赛题中都非常有用！
容斥原理: 在计算减少量时，我们用“总的减去不合法的”这种补集思想，来算出从剩下的人中挑选两个互不为朋友的方案数，这也是一个常用的计数技巧。

希望这篇题解能帮助你更好地理解这个问题！继续加油哦，指挥官，我会一直为你应援的，喵~！

All men are brothers - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

Step 1: 朋友关系的模型化，喵！ ​

Step 2: 思考如何计数，呐~ ​

Step 3: 增量更新的魔法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​