概要

各駅から次の駅が一意に決まる路線で、駅 \(1\) から出発して駅 \(N\) に着くまでに「訪れる駅の総数（両端含む）」を数えます。

考察

• この問題では、駅 \(i\)（\(1 \le i \le N-1\)）から行ける先は必ず \(P_i\) の 1つだけ です。つまり「次にどこへ行くか」で迷うことがなく、移動経路は駅 \(1\) から 一直線に（決め打ちで） たどれます。
• 入力は「駅 \(1\) から駅 \(N\) に到達可能」が保証されています。したがって、駅 \(1\) から始めて [ 1 \rightarrow P1 \rightarrow P{P_1} \rightarrow \cdots ] と進めば、必ずどこかで駅 \(N\) に到達します。
• 素朴に「全ての辺を使ってグラフ探索（BFS/DFS）して最短距離…」のようなことを考えると、実はこの問題では不要です（分岐がないため）。また DFS を再帰で書くと \(N\) が最大 \(2 \times 10^5\) なので再帰深さ制限で落ちる可能性があります。
• そこで、現在地 cur を更新しながら、駅 \(N\) に着くまでカウントを増やすだけで解けます。

例： - \(N=5\)、\(1\to 3\to 4\to 5\) なら訪れる駅は \(\{1,3,4,5\}\) で答えは \(4\)。

アルゴリズム

1. 配列 \(P\) を読み込む（\(P_i\) は \(i=1\) から \(N-1\) まで）。
2. cur = 1（現在地）、cnt = 1（駅 \(1\) を既に訪れたので 1）で開始する。
3. cur != N の間、以下を繰り返す：
   • cur = P[cur] として次の駅へ進む
   • cnt += 1 として訪れた駅数を増やす
4. cur == N になったら cnt を出力する。

計算量

• 時間計算量: \(O(K)\)（\(K\) は \(1\) から \(N\) までに実際に移動する回数。最大でも \(O(N)\)）
• 空間計算量: \(O(N)\)（配列 \(P\) を保持するため）

実装のポイント

• 駅数のカウントは「駅1も含む」ので、初期値を cnt = 1 にします（到着駅 \(N\) もループ内で加算されます）。

• \(N\) が大きいので、入力は sys.stdin.buffer.read() でまとめて読むと高速です。

• 添字を問題文通りに扱うため、配列 \(P\) は 1-indexed（長さ \(N+1\)）にしています。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    P = [0] * (N + 1)
    for i in range(1, N):
        P[i] = data[i]

    cur = 1
    cnt = 1
    while cur != N:
        cur = P[cur]
        cnt += 1

    print(cnt)

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。