← 返回题目列表

AtCoder · awc0034_b

B. 从车站到车站

中文机器翻译题面 查看原题

分数: 300 分

问题陈述

高桥正在调查一条铁路线。这条线有 N 站,编号自 1 to N.

该生产线具有特殊的结构。从车站出发 i (1 \leq i \leq N-1),只有一列火车前往车站 P_i 已运行。在这里, P_i 是介于 1 和 N,包含在内,不同于 i。车站 N 为最终目的地,该站无列车出发 N.

高桥在车站出发 1 并反复登上每个车站唯一可用的火车,目标是到达车站 N。当他到达车站时旅程结束 N.

给出的输入使得从站开始 1 重复上述过程,他总会到达车站 N 在有限次数的移动中无需访问同一站两次。

查找从车站访问过的车站数量 1 直到到达车站 N。包括出发站(车站 1)和到达站(站 N)在计数中。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \leq N (1 \leq i \leq N-1)
  • P_i \neq i (1 \leq i \leq N-1)
  • 保证站 从车站可到达 N 从车站可以到达 1 无需访问同一车站两次
  • 所有输入值均为整数

输入

N
P_1 P_2 \cdots P_{N-1}
  • 第一行包含一个整数 N,代表站数。
  • 第二行包含 N-1 整数 P_1, P_2, \ldots, P_{N-1} 以空格分隔。 P_i 表示从车站乘火车可到达的下一站的编号 i。由于没有火车从车站出发 未给出 N, P_N 。

输出

一行打印从车站访问过的车站数量 1 直到到达车站 N (包括两个站 1 和车站 N).


示例输入 1

5
2 4 5 5

示例输出 1

4

示例输入 2

8
3 5 7 2 8 4 6

示例输出 2

8

示例输入 3

10
2 3 4 5 6 7 8 9 10

示例输出 3

10