CSP-S 提高级 · CSP 2019 提高级第一轮 第 17 题

2.

#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;
}

• 判断题

1) （1 分）输入的 $a$ 和 $b$ 值应在 $[0, n-1]$的范围内。（） 2) （1 分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（） 3) 若输入的 $a$ 和 $b$ 值均在 $[0, n-1]$ 的范围内，则对于任意 $0\leq i<n$ 都有 $0 \leq fa[i] <n$ （） 4) 若输入的 $a$ 和 $b$ 值均在 $[0, n-1]$ 的范围内，则对于任意 $0\leq i<n$ 都有 $1 \leq cnt[i]\leq n$ （）

• 选择题

5) 当 $n$ 等于50时，若 $a,b$ 的值都在 $[0,49]$ 的范围内，且在第 $25$ 行时 $x$ 总是不

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题核心是读懂并查集合并时的计数逻辑：每次合并两个集合，把两集合大小的乘积累加到 ans 里，最后 ans 就是所有节点对在合并前分属不同集合的总次数。

容易把 cnt 更新的位置搞错，以为合并后才累加；或者误以为题目保证 x!=y，从而忽略 x=y 时 ans 不变的情况；还有对第 3 问的 fa 范围判断，只看到初始化 fa[i]=i 就以为永远合法，忘了后续 fa[x]=y 中 y 可能超出 n-1 的极端输入（虽然题目通常保证合法，但严谨性要考）。

2019 CSP 提高级 第 17 题：阅读程序——并查集

一、这题考什么？

这道题是一道典型的程序阅读理解题，但它的核心考点非常集中： 1. 并查集（Disjoint Set Union, DSU）的基本操作：初始化、getRoot 找根、合并。 2. 组合计数的含义：ans += cnt[x] * cnt[y] 到底在算什么？ 3. 递归函数的执行流程：getRoot 没有路径压缩，纯递归。 4. 边界与不变量：数组下标范围、fa 和 cnt 的取值范围。 5. 时间复杂度：无路径压缩的并查集合并操作的总耗时。

命题人挖坑点在于：代码很短，但逻辑很“绕”。ans 的累加位置在合并之前，cnt 的更新在合并之后，这两个动作的顺序决定了 ans 的含义。很多学生看到 cnt[y] += cnt[x] 就以为那是合并后的状态，从而误判 ans 的计算时机。