CSP-S 2026 第一轮 第 31 题：程序（三）：程序输出的 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。

程序输出的 ans 表示的是（ ）。

选项

• A. 树中距离最远的两个结点之间路径所经过的边数
• B. 根结点 1 到最远叶子结点之间路径所经过的边数
• C. 树中叶子结点的个数
• D. 所有结点的父结点编号之和

答案

A

题解

选 A。ans 表示树的直径，即树中距离最远的两个结点之间路径的边数。

关键是理解 f 和 ans 的更新。

1. f[u] 表示从结点 u 向下走的最长路径的边数。

由于 fa[i] < i，程序从大到小遍历时，子结点一定先于父结点处理。因此，处理结点 i 时，f[i] 已经计算完毕。

令 p = fa[i]，则： ``cpp f[p] = max(f[p], f[i] + 1); ` 表示从父结点 p 经过 i 向下走，最长能走 f[i] + 1` 条边。

2. ans 记录两条向下路径拼接后的最大长度。

更新 ans 时： ``cpp ans = max(ans, f[p] + f[i] + 1); ` 此时还没有用 i 更新 f[p]`，所以：

• f[p] 是从 p 经过之前处理过的其他子结点向下走的最长距离；若没有，则为 0。
• f[i] + 1 是从 p 经过当前子结点 i向下走的最长距离。

两条路径在 p 处拼接，就形成一条两端结点之间的路径。

例如： ``text 1 / \ 2 3 / \ 4 5 ` 在根结点处，两侧最长距离都是 2，于是得到： `text 4 → 2 → 1 → 3 → 5 ` 共 2 + 2 = 4` 条边。

树中任意两点之间的路径，都可以在它们的最近公共祖先处这样拆开。因此取所有候选路径的最大值，就是树的直径，选 A。