CSP-S 2019 第一轮 第24题：若输入的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$ 都有 $0 \leq fa[i] <n$ （）

选项

• T. 正确
• F. 错误

答案

T

题解

答案：T，正确。

看 fa 数组的初始化和修改：

1. 初始化：fa[i] = i，因此对任意 \(0\le i<n\)，都有 \(0\le fa[i]<n\)。
2. 后续修改：唯一修改 fa 的语句是：

``cpp fa[x] = y; ` 其中 y = getRoot(b)，返回的是某个节点的编号，仍在 \([0,n-1]\) 内，因此赋值后 fa[x]` 依然满足范围要求。其他元素没有改变。

所以，fa[i] 始终是合法的节点编号，命题正确。