Overview

Since each child passes the ball to exactly one person, the transitions form a “functional graph” (a directed graph where each node has out-degree 1). The answer to each query can be computed as “distance from the starting point to the cycle + length of the cycle entered.”

Analysis

Key Observation

Since child \(i\) always passes to \(T_i\), viewed as a graph, this is a directed graph where each vertex has out-degree exactly 1 (a functional graph).

This type of graph always consists of: - Several cycles (closed loops) - Trees flowing into those cycles (trees when viewed in reverse direction)

Tracing the game’s progression from starting point \(S\): 1. Keep moving in one direction until returning to the same vertex 2. The game ends the moment someone tries to pass to a “child who has already received the ball”

In other words, the path traced from \(S\): - Proceeds in a straight line without branching - Eventually reaches a cycle, and stops when “the next person to pass to has already been visited” within that cycle

Therefore, the number of distinct people who received the ball is the sum of: - The number of vertices passed through before entering the cycle (the straight-line portion outside the cycle) - The number of vertices traversed in one full loop of the cycle (the cycle length)

Thus the answer is: $\(\text{dist}[S] + \text{cycle\_size}[S]\)\( (\)\text{dist}[S]\(: the number of edges from \)S\( to reach the cycle; 0 if \)S$ is on the cycle).

Why a Naive Solution is Too Slow

If we “maintain a visited set and actually simulate” for each query, the worst case is \(O(N)\) per query, resulting in \(O(NQ)\) overall, which is too slow (with a maximum of \(2\times 10^5\), this is fatal).

Therefore, we precompute “distance to cycle” and “length of the associated cycle” for all vertices, and answer each query in \(O(1)\).

Algorithm

1. Extract Vertices on Cycles (Removing Vertices with In-degree 0)

Vertices not contained in any cycle (tree-side vertices) can be eliminated through a “deletion chain starting from in-degree 0 vertices.”

Procedure: 1. Count the in-degree \(\text{indeg}[v]\) of each vertex 2. Enqueue all vertices with in-degree 0 3. Dequeue a vertex, mark it as “deleted,” and decrease the in-degree of its destination \(T_v\) by 1
If the in-degree becomes 0, enqueue it

After this process, the vertices that remain undeleted are exactly the vertices on cycles.

2. Traverse Each Cycle to Determine “Cycle Length”

Starting from any unvisited vertex among those remaining (not deleted), following \(T\) will trace exactly one full cycle.

• For each vertex \(v\) on a cycle, set:
  • \(\text{dist}[v] = 0\)
  • \(\text{cycle\_size}[v] = (\text{length of that cycle})\)

3. Propagate Information to Tree Parts via Reverse-Edge BFS

For each edge \(i \to T_i\), prepare an adjacency list rev holding the reverse edge \(T_i \to i\).

Starting BFS from all vertices on cycles (vertices with \(\text{dist}=0\)): - Expanding layer by layer from the cycle outward - For each tree-side vertex \(v\), set: $\(\text{dist}[v] = \text{dist}[u] + 1,\quad \text{cycle\_size}[v] = \text{cycle\_size}[u]\)\( (where \)u\( is the vertex closer to the cycle in the direction of \)v$’s transition)

4. Answering Queries

For each query \(S\), output: $\(\text{dist}[S] + \text{cycle\_size}[S]\)$

(Example) If it takes 3 steps from \(S\) to the cycle, and the cycle length is 5, then the number of people who receive the ball is \(3+5=8\).

Complexity

• Time complexity: \(O(N+Q)\)
  (In-degree deletion \(O(N)\), cycle detection \(O(N)\), BFS \(O(N)\), each query \(O(1)\))
• Space complexity: \(O(N)\)
  (Arrays, reverse-edge list, queue, etc.)

Implementation Notes

• Building a reverse-edge list rev makes it convenient to BFS from cycles to trees all at once.

• Cycle extraction using the “remove in-degree 0 vertices” technique is a classic method that works powerfully for cycle detection in functional graphs.

• Although queries are independent, the graph itself is the same, so we precompute and achieve \(O(1)\) response per query.

  Source Code

import sys
from collections import deque

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    it = iter(data)
    N = next(it)
    Q = next(it)

    T = [0] * (N + 1)
    indeg = [0] * (N + 1)
    rev = [[] for _ in range(N + 1)]

    for i in range(1, N + 1):
        t = next(it)
        T[i] = t
        indeg[t] += 1
        rev[t].append(i)

    removed = [False] * (N + 1)
    dq = deque(i for i in range(1, N + 1) if indeg[i] == 0)
    while dq:
        v = dq.popleft()
        removed[v] = True
        u = T[v]
        indeg[u] -= 1
        if indeg[u] == 0:
            dq.append(u)

    dist = [-1] * (N + 1)
    cycsize = [0] * (N + 1)
    in_cycle_visited = [False] * (N + 1)

    # Identify cycles and set dist=0, cycsize for cycle nodes
    for i in range(1, N + 1):
        if not removed[i] and not in_cycle_visited[i]:
            nodes = []
            cur = i
            while True:
                in_cycle_visited[cur] = True
                nodes.append(cur)
                cur = T[cur]
                if cur == i:
                    break
            sz = len(nodes)
            for v in nodes:
                dist[v] = 0
                cycsize[v] = sz

    # BFS from cycle nodes to assign dist and cycsize to tree nodes
    dq = deque([i for i in range(1, N + 1) if dist[i] == 0])
    while dq:
        u = dq.popleft()
        for v in rev[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                cycsize[v] = cycsize[u]
                dq.append(v)

    out = []
    for _ in range(Q):
        s = next(it)
        out.append(str(dist[s] + cycsize[s]))

    sys.stdout.write("\n".join(out))

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.