CSP-S 2019 第一轮 第26题：当n等于 50 时，若 a、b 的值都在[0,49］的范围内，且在第 25 行时

题目

#include <iostream>
using namespace std;

const int maxn = 1000;
int n;
int fa[maxn], cnt[maxn];

int getRoot(int v) {
    if (fa[v] == v) return v;
    return getRoot(fa[v]);
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        fa[i] = i;
        cnt[i] = 1;
    }
    int ans = 0;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, x, y;
        cin >> a >> b;
        x = getRoot(a);
        y = getRoot(b);
        ans += cnt[x] * cnt[y];
        fa[x] = y;
        cnt[y] += cnt[x];
    }
    cout << ans << endl;
    return 0;
}

当 $n$ 等于50时，若 $a,b$ 的值都在 $[0,49]$ 的范围内，且在第 $25$ 行时 $x$ 总是不等于 $y$，那么输出为（）。

选项

• A. $1276$
• B. $1176$
• C. $1225$
• D. $1250$

答案

C

题解

答案选 C，\(1225\)。

这段程序使用了并查集：

• getRoot(a) 找到 \(a\) 所在集合的根。
• cnt[x] 表示以 \(x\) 为根的集合中有多少个元素。
• fa[x] = y 将两个集合合并。

关键在这一句：

``cpp ans += cnt[x] * cnt[y]; ``

假设两个集合分别有 \(p\)、\(q\) 个元素，合并后，新增了 \(p\times q\) 对“处于同一集合中的元素”：从两个集合各选一个元素即可。

初始时，50 个元素各自独立，同一集合内的元素对数为 0。循环执行 \(50-1=49\) 次，且每次都有 \(x\ne y\)，因此每次都合并两个不同的集合，集合数量减少 1。最终，50 个元素全部处于同一个集合中。

每对不同元素恰好在它们第一次进入同一集合时被统计一次，所以：

\[ \text{ans}=\binom{50}{2}=\frac{50\times49}{2}=\boxed{1225}. \]