CSP-S 2026 第一轮 第 33 题：程序（三）：当 n=10，满足输出为 9 的合法输入种类数为

题目

#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=10$，满足输出为 9 的合法输入种类数为（ ）。

选项

• A. 0
• B. 9
• C. 256
• D. 512

答案

C

题解

答案是 C．256。

先看程序计算的是什么：

由于 fa[i] < i，按编号从大到小处理时，结点 i 的后代都已处理完。此时：

• f[i] 表示从 i 向下走的最大距离。
• f[fa[i]] + f[i] + 1 将父结点之前处理过的最长分支，与经过 i 的分支连接起来，得到一条路径的长度。
• 因此，最终的 ans 就是树的直径（最长路径的边数）。

10 个结点的树，直径为 9，当且仅当整棵树是一条链。 接下来只需统计满足父结点编号小于子结点编号的链有多少种。

以结点 1 为根，这条链可以分成从 1 出发的两条分支，其中一条允许为空。因为沿分支远离根时编号必须递增，所以只要确定每条分支包含哪些结点，它们的顺序就唯一确定了。

为了避免交换两条分支造成重复计数，规定：

• 包含结点 2 的分支叫第一条分支；
• 剩余结点 3～10，每个都可以独立选择放入第一条或第二条分支。

共有 8 个结点，每个有 2 种选择，所以合法输入数为 \[ \boxed{2^8=256}. \]