概要

この問題は、各頂点からちょうど1本の有向辺が出ているグラフ（Functional Graph）上で、指定された頂点からスタートして、すでに訪れた頂点に再び到達するまでに何個の異なる頂点を通るかを求める問題です。

各クエリに対して愚直にシミュレーションを行うと実行時間制限に間に合わないため、事前にすべての頂点からスタートしたときの答えを \(O(N)\) で求めておくアプローチをとります。

---

考察

グラフの構造（Functional Graph）

各子供 \(i\) は必ず一意な相手 \(T_i\) にボールを渡します。これは、頂点数 \(N\)、辺の数 \(N\) で、すべての頂点からちょうど1本の有向辺が出ているグラフとみなせます。このようなグラフは Functional Graph と呼ばれ、以下のような特徴を持ちます。

• どの頂点から出発しても、遷移を繰り返すと必ずどこかのサイクル（閉路）に到達し、その後はサイクル内を回り続ける。
• グラフ全体は、いくつかの「サイクル」と、そのサイクルに向かって合流する「木（枝の部分）」から構成される。

愚直な方法とその問題点

クエリごとに、ボールが同じ人に渡るまで実際に遷移をシミュレーションすると、1回のクエリにつき最悪 \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、 \(N, Q \le 2 \times 10^5\) の制約下では実行時間制限（TLE）になってしまいます。

効率的な解決策

各クエリは独立ですが、スタートする頂点が同じであればゲームの結果（訪れる人数）は常に同じです。したがって、すべての頂点について、そこからスタートしたときに訪問する異なる子供の人数をあらかじめ前計算しておけば、各クエリには \(O(1)\) で答えることができます。

頂点 \(u\) からスタートしたときの答えを \(ans[u]\) とします。 1. 頂点 \(u\) がサイクル上にある場合： サイクル上のどこからスタートしても、サイクルをちょうど1周して元の位置に戻った時点でゲームが終了します。したがって、 \(ans[u] = (\text{そのサイクルの長さ})\) となります。 2. 頂点 \(u\) がサイクル外（枝の部分）にある場合： 頂点 \(u\) の次の遷移先は \(T_u\) です。 \(u\) からスタートすると、1歩進んで \(T_u\) に到達し、そこから先は \(T_u\) からスタートしたときと全く同じ経路をたどります。したがって、 \(ans[u] = ans[T_u] + 1\) という関係が成り立ちます。

この性質を利用して、サイクル上の頂点の答えをまず確定させ、次にサイクルに向かって合流する枝の部分の答えを後ろから（サイクルに近い順に）決定していくことで、すべての頂点の答えを \(O(N)\) で求めることができます。

---

アルゴリズム

提示されたコードでは、以下の手順で \(O(N)\) の前計算を行っています。

1. トポロジカルソートによる「枝」と「サイクル」の分離

まず、各頂点の入次数（その頂点に流れ込む辺の数）を計算します。 入次数が \(0\) の頂点は、絶対にサイクルに含まれません（枝の先端＝葉です）。 1. 入次数が \(0\) の頂点をキューに入れます。 2. キューから頂点 \(u\) を取り出し、トポロジカルソートの順序リスト topo_order に追加します。 3. \(u\) の遷移先 \(v = T_u\) の入次数を \(1\) 減らします。もし \(v\) の入次数が \(0\) になったら、 \(v\) もキューに追加します。 4. キューが空になるまでこれを繰り返します。

この処理が終わったとき： - topo_order には、サイクルに含まれない「枝」の部分の頂点が、葉からサイクルに向かう順で格納されます。 - 入次数（deg）が \(1\) 以上のまま残っている頂点は、すべてサイクル上の頂点となります。

2. サイクルの長さを求める

入次数が \(1\) 以上の頂点を探索し、サイクルを検出します。 未訪問のサイクル上の頂点から出発して、遷移先をたどりながらサイクルを1周し、その長さ \(L\) を数えます。そして、そのサイクルに含まれるすべての頂点 \(v\) に対して \(ans[v] = L\) とします。

3. 枝の部分の答えを動的計画法（DP）で求める

topo_order には、葉からサイクルに向かう順で頂点が並んでいます。 これを逆順（サイクルに合流する手前の頂点から、葉に向かう順）に走査します。 逆順に処理することで、頂点 \(u\) を処理するとき、その遷移先 \(T_u\) の答え \(ans[T_u]\) はすでに確定していることが保証されます。 したがって、以下の遷移式で順次答えを決定できます。 $\(ans[u] = ans[T_u] + 1\)$

4. クエリへの回答

前計算した \(ans\) 配列を参照し、各クエリ \(S_j\) に対して \(ans[S_j]\) を出力します。

---

計算量

• 時間計算量: \(O(N + Q)\)

  • 入次数の計算、トポロジカルソート、サイクルの検出、枝部分のDPの各ステップにおいて、すべての頂点と辺を定数回ずつしか走査しないため、前計算は \(O(N)\) で完了します。
  • 各クエリには \(O(1)\) で答えられるため、クエリ全体の処理は \(O(Q)\) です。
  • よって、全体の時間計算量は \(O(N + Q)\) となり、実行時間制限に余裕で間に合います。

• 空間計算量: \(O(N)\)

  • グラフの遷移先を格納する配列 \(T\)、入次数配列 deg、トポロジカルソートの順序を格納するリスト topo_order、答えを格納する配列 ans など、すべてサイズ \(O(N)\) の配列で管理されているため、空間計算量は \(O(N)\) です。

---

実装のポイント

• トポロジカルソートの逆順利用: 枝の部分を処理する際、reversed(topo_order) を使用することで、遷移先が必ず計算済みになるように工夫されています。これにより、再帰関数（DFS）によるスタックオーバーフローの心配がなく、安全かつ高速にDPを行うことができます。

• 高速な入出力: Pythonにおいてクエリ数や出力行数が多い場合、print() を繰り返すとボトルネックになります。sys.stdin.read や sys.stdout.write を用いて一括で入出力を行うことで、実行時間を大幅に削減しています。

  ソースコード

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    N = int(input_data[0])
    Q = int(input_data[1])

    T = [0] + [int(x) for x in input_data[2 : N + 2]]
    queries = [int(x) for x in input_data[N + 2 : N + 2 + Q]]

    deg = [0] * (N + 1)
    for i in range(1, N + 1):
        deg[T[i]] += 1

    queue = [i for i in range(1, N + 1) if deg[i] == 0]
    topo_order = []
    ptr = 0
    while ptr < len(queue):
        u = queue[ptr]
        ptr += 1
        topo_order.append(u)
        v = T[u]
        deg[v] -= 1
        if deg[v] == 0:
            queue.append(v)

    ans = [0] * (N + 1)
    visited = [False] * (N + 1)

    for i in range(1, N + 1):
        if deg[i] > 0 and not visited[i]:
            cycle = []
            curr = i
            while not visited[curr]:
                visited[curr] = True
                cycle.append(curr)
                curr = T[curr]
            L = len(cycle)
            for node in cycle:
                ans[node] = L

    for u in reversed(topo_order):
        ans[u] = ans[T[u]] + 1

    out = [str(ans[S]) for S in queries]
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。