CSP-S 2019 第一轮 第25题：若输入的a和b值均在[θ，n-1]的范围内，则对于任意0≤i<n，都

题目

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

若输入的 $a$ 和 $b$ 值均在 $[0, n-1]$ 的范围内，则对于任意 $0\leq i<n$ 都有 $1 \leq cnt[i]\leq n$ （）

选项

• T. 正确
• F. 错误

答案

F

题解

选 F（错误）。

代码没有判断 x 和 y 是否为同一个根。当 x == y 时，语句

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

会使该根的 cnt 翻倍，因此可能超过 n。

例如输入：

``text 3 0 1 0 1 ``

• 初始时：cnt[0] = cnt[1] = cnt[2] = 1。
• 第一次合并：x = 0, y = 1，得到 fa[0] = 1、cnt[1] = 2。
• 第二次合并：0 和 1 的根都是 1，因此 x = y = 1，执行后 cnt[1] = 4。

此时 cnt[1] = 4 > n = 3，所以题目中的结论不成立。