Overview

On a route where the next station from each station is uniquely determined, we count the “total number of stations visited (including both endpoints)” when departing from station \(1\) until arriving at station \(N\).

Analysis

• In this problem, from station \(i\) (\(1 \le i \le N-1\)), there is exactly one destination \(P_i\). This means there is no ambiguity about “where to go next,” and the travel path can be traced in a straight line (deterministically) from station \(1\).
• The input guarantees that “station \(N\) is reachable from station \(1\).” Therefore, starting from station \(1\) and following [ 1 \rightarrow P1 \rightarrow P{P_1} \rightarrow \cdots ] we will always reach station \(N\) at some point.
• You might naively think about “using all edges to do graph search (BFS/DFS) to find the shortest distance…”, but this is actually unnecessary for this problem (since there are no branches). Also, if you write DFS recursively, \(N\) can be up to \(2 \times 10^5\), so you might hit the recursion depth limit.
• Therefore, the problem can be solved by simply updating the current position cur and incrementing a counter until we reach station \(N\).

Example: - If \(N=5\) and \(1\to 3\to 4\to 5\), the visited stations are \(\{1,3,4,5\}\) and the answer is \(4\).

Algorithm

1. Read the array \(P\) (\(P_i\) for \(i=1\) to \(N-1\)).
2. Start with cur = 1 (current position) and cnt = 1 (since station \(1\) is already visited, initialize to 1).
3. While cur != N, repeat the following:
   • Move to the next station by setting cur = P[cur]
   • Increment the number of visited stations with cnt += 1
4. When cur == N, output cnt.

Complexity

• Time complexity: \(O(K)\) (\(K\) is the actual number of moves from \(1\) to \(N\). At most \(O(N)\))
• Space complexity: \(O(N)\) (for storing the array \(P\))

Implementation Notes

• The station count includes station 1, so we initialize with cnt = 1 (the destination station \(N\) is also added within the loop).

• Since \(N\) can be large, reading input all at once with sys.stdin.buffer.read() is faster.

• To handle indices as described in the problem statement, the array \(P\) is 1-indexed (with length \(N+1\)).

  Source Code

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()

This editorial was generated by gpt-5.2-high.