ABC263B Ancesto
题目分析¶
本题给定了一个家谱关系：共 n 个人，其中第 i 个人的上一代是 $p_i$（且满足 $p_i < i$）。
题目保证输入合法：即第 $1$ 个人没有上一代，其余每个人都指向编号比自己小的某个祖先。
目标是计算从第 n 个人追溯到第 1 个人之间相隔多少代，也可以理解为从 n 开始沿着上一代一路向上跳，直到跳到第 1 个人，问跳了多少次。
解题思路¶
- 把每个人的上一代信息存进数组
p[i]； - 从第
n个人开始，一直向上追溯到1； - 每追溯一次，就表示隔了一代，计数器加一；
- 最后输出这个计数器的值即可。
实现步骤¶
- 定义数组
p[55]，将输入存到下标从2到n。存储上一代信息； - 定义变量
x = n表示当前人； - 定义计数器
cnt = 0； - 使用
while (x != 1)循环：- 更新
x = p[x]； cnt++；
- 更新
- 最后输出
cnt。
复杂度分析¶
- 时间复杂度：$O(n)$，最多从
n向上跳到1，跳n次以内； - 空间复杂度：$O(n)$，用于存储上一代信息的数组。
总结¶
- 本题本质是从
n一路向上走家谱链，直到走到1，问路径长度； - 只需要模拟跳代过程，不涉及复杂算法；
- 输入小，直接用数组和循环处理即可。