📝 题目大意

有 $n$ 个人，第 $i$ 个人的上一代（父亲）是 $p_i$（保证 $p_i < i$）。求从第 $n$ 个人追溯到第 $1$ 个人一共经过了几代人。

💡 解题思路

1. 题目分析：

   • 约束 $p_i < i$ 保证了这是一个以 $1$ 为根、编号递增的有根树，且 $1$ 必为祖先，不会出现环。
   • $n$ 的范围在 AtCoder ABC 的 B 题中通常为 $N \le 50$ 或 $N \le 100$，直接模拟即可。

2. 算法推导：

   • 以 $p_i$ 作为父指针，将每个人的父亲存入数组 p[i]（p[1] 无父亲，无需使用）。
   • 从 $n$ 出发，不断令 current = p[current]，即沿着父亲链向上追溯，直到到达 $1$。
   • 每向上走一步，代际计数 steps 加 $1$，最终 steps 即为答案。

3. 边界与细节：

   • 输入 $p_2$ 到 $p_n$，共 $n-1$ 个数，注意下标从 $2$ 开始。
   • 当 $n=1$ 时不会出现（题目隐含 $n \ge 2$），但即使出现，循环不会执行，steps 为 $0$。
   • 保证 $p_i < i$ 意味着编号严格递增，不会出现 $p_i = i$ 的自环，也不会出现死循环。

⏱️ 复杂度分析

• 时间复杂度：$O(N)$，最坏情况下链长为 $N$，每条边访问一次。
• 空间复杂度：$O(N)$，用于存储父指针数组。

💻 标准代码 (C++)

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> p(n + 1);  // p[i] 表示第 i 个人的父亲
    // 读入 p_2 到 p_n
    for (int i = 2; i <= n; i++) {
        cin >> p[i];
    }
    int current = n;  // 从第 n 个人开始追溯
    int steps = 0;    // 记录经过的代数
    // 沿着父亲链向上走，直到到达第 1 个人
    while (current != 1) {
        current = p[current];  // 跳到父亲
        steps++;               // 代数 +1
    }
    cout << steps << endl;
    return 0;
}