CSP-S 2026 第一轮 第 28 题：程序（三）：当 n=5，fa[2]~fa[5]=1,2,3,4 时

题目

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

当 $n=5$，$fa[2] \sim fa[5]={1, 2, 3, 4}$ 时，程序输出 4。（ ）

选项

• √. 正确
• ×. 错误

答案

√

题解

选 √（正确）。

父结点依次为 1,2,3,4，所以这棵树是一条链：

``text 1 — 2 — 3 — 4 — 5 ``

f 和 ans 都是全局变量，初始值为 0。循环从 i=5 倒着执行到 i=2，每次先更新 ans，再更新父结点的 f：

因此最终输出 4，题目说法正确。

这段程序实际上求的是树的直径，即两个结点之间路径的最大边数。这条链有 5 个结点、4 条边，所以直径为 4。