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

题目

#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=7$，$fa[2] \sim fa[7]={1, 1, 2, 2, 3, 3}$ 时，输出为（ ）。

选项

• A. 2
• B. 3
• C. 4
• D. 5

答案

C

题解

答案是 C. 4。

父结点数组对应的树为：

``text 1 / \ 2 3 / \ / \ 4 5 6 7 ``

f 和 ans 都是全局变量，初始值为 0。程序从 i=7 到 i=2 倒序处理：

• f[u]：从结点 u 向下走，当前找到的最长路径长度（按边数计算）。
• f[fa[i]] + f[i] + 1：把父结点已有的向下路径，与经过 i 的向下路径拼接，得到一条候选路径。
• ans：记录找到的最长路径长度。

逐步执行如下，第三列使用的是本轮更新前的 f 值：

因此输出 4。它对应树的最长路径，例如 4 → 2 → 1 → 3 → 6，共有 4 条边，注意不是数结点个数。