CSP-S 2026 第一轮 第 30 题：程序（三）：将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后

题目

#include <iostream>
using namespace std;
int n, fa[100007], f[100007], ans;
int main() {
    cin >> n;
    for (int i = 2; i <= n; ++i) {
        cin >> fa[i];
    }
    for (int i = n; i >= 2; --i) {
        if (f[fa[i]] + f[i] + 1 > ans) {
            ans = f[fa[i]] + f[i] + 1;
        }
        if (f[i] + 1 > f[fa[i]]) {
            f[fa[i]] = f[i] + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

说明：输入第一行为结点个数 $n$，第二行为 $n - 1$ 个整数，依次表示结点 2—$n$ 的父结点编号，满足 $2 \le n \le 10000$ 且 $1 \le fa[i] < i$，根结点为 1。

将第 10—12 行与第 13—15 行两个 if 语句的顺序交换后，程序输出结果不受影响。（ ）

选项

• √. 正确
• ×. 错误

答案

×

题解

选 ×（错误）。两个 if 的顺序会影响结果，因为第二个 if 会修改第一个 if 用到的 f[fa[i]]。

用最简单的输入举例： ``text 2 1 ` 即结点 1 是根，结点 2 是它的孩子。全局数组 f 和变量 ans` 初始都为 0。

按题中顺序执行，当 i = 2 时：

1. 先更新 ans = f[1] + f[2] + 1 = 1。
2. 再更新 f[1] = f[2] + 1 = 1。

最终输出 1。

交换两个 if 后：

1. 先更新 f[1] = f[2] + 1 = 1。
2. 再更新 ans = f[1] + f[2] + 1 = 2。

最终输出 2。

因此，交换前后输出不同，题目说法错误。原顺序是先用父结点已有的信息计算答案，再把当前孩子的信息合并进去；交换后，计算答案时就可能重复使用当前孩子这条分支。