CSP-S 2026 第一轮 第 29 题：程序（三）：程序输出前，f[1] 的值一定等于 ans 的值

题目

#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。

程序输出前，f[1] 的值一定等于 ans 的值。（ ）

选项

• √. 正确
• ×. 错误

答案

×

题解

选 ×，错误。

给一个最简单的反例：根结点 1 有两个孩子 2、3。

``text 1 / \ 2 3 ``

对应输入： ``text 3 1 1 ``

全局数组和变量初始值都为 0，循环过程如下：

因此，输出前 f[1] = 1，ans = 2，两者不相等。

从含义上看，f[1] 是根到最远叶子的距离，而 ans 是树的直径（任意两点间的最大距离），距离均按边数计算。本例中，最长路径为 2 → 1 → 3，长度为 2。