2019年信奥赛C++提高组csp-s初赛真题及答案解析（阅读程序第2题）
第2题
01 #include <iostream>
02 using namespace std;
03
04 const int maxn = 1000;
05 int n;
06 int fa[maxn], cnt[maxn];
07
08 int getRoot(int v) {
09 if (fa[v] == v) return v;
10 return getRoot(fa[v]);
11 }
12
13 int main() {
14 cin >> n;
15 for (int i = 0; i < n; ++i) {
16 fa[i] = i;
17 cnt[i] = 1;
18 }
19 int ans = 0;
20 for (int i = 0; i < n – 1; ++i) {
21 int a, b, x, y;
22 cin >> a >> b;
23 x = getRoot(a);
24 y = getRoot(b);
25 ans += cnt[x] * cnt[y];
26 fa[x] = y;
27 cnt[y] += cnt[x];
28 }
29 cout << ans << endl;
30 return 0;
31 }
- 判断题
（1 分）输入的 a和 b 值应在 [0,n−1]的范围内。（）
A. 正确 B. 错误
（1 分）第 16 行改成 fa[i] = 0;，不影响程序运行结果。（）
A. 正确 B. 错误
若输入的 a和 b值均在 [0,n−1]的范围内，则对于任意 0≤i<n 都有 0≤fa[i]<n（）
A. 正确 B. 错误
若输入的 a和 b 值均在 [0,n−1]的范围内，则对于任意 0≤i<n都有 1≤cnt[i]≤n （）
A. 正确 B. 错误
- 选择题
A. 1276
B. 1176
C. 1225
D. 1250
A. O(n)
B. O(logn)
C. O(
n
2
n^2
n2)
D. O(nlogn)
答案及题解
题目分析
该程序实现了一个简单的并查集（无路径压缩），初始时每个节点自成一集，cnt[i] 记录以 i 为根的集合大小。读入 n-1 条边，每次合并两个不同集合时，将两集合大小之积累加到答案 ans 中，并更新父节点和集合大小。最终输出 ans。
判断题
程序中使用 a 和 b 作为数组下标，若超出范围会导致越界访问，因此输入必须在此范围内。该说法正确。 答案：A
原初始化使每个节点的父节点指向自身，改为全部指向 0 后，所有节点初始根均为 0，导致后续合并时 x 与 y 总是相等，结果完全改变。该说法错误。 答案：B
fa 数组始终存储节点索引，初始为自身，合并时也只赋值为已有节点，因此始终在 [0, n-1] 内。该说法正确。 答案：A
cnt 在合并时只更新根节点，非根节点保持初始值 1。但若出现自环或重复合并同一集合（如输入环），根节点大小可能超过 n（例如 n=3 时两次自环可使 cnt[0]=4）。因此该结论不一定成立。 答案：B
选择题
每次合并两个不同集合，新增的连通点对数为两集合大小之积，且每个点对恰好被计数一次。最终所有点连通，总点对数为
50
×
49
2
=
1225
\\frac{50 \\times 49}{2} = 1225
250×49=1225。 答案：C
getRoot 为递归实现且无路径压缩，最坏情况下树高为 O(n)，每次查找需 O(n)。循环 n-1 次，总复杂度 O(n²)。 答案：C
专栏推荐：信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"########## 一站式掌握信奥赛知识! ##########";
cout<<"############# 冲刺信奥赛拿奖! #############";
cout<<"###### 课程购买后永久学习，不受限制! ######";
return 0;
}
1、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划： https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL： https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践： https://blog.csdn.net/weixin_66461496/category_13113932.html
2、csp信奥赛冲刺一等奖有效刷题题解：
CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新） https://blog.csdn.net/weixin_66461496/category_13125089.html
3、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）： https://blog.csdn.net/weixin_66461496/category_13117178.html
4、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转 
· 文末祝福 ·
#include<bits/stdc++.h>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
