概要

この問題は、各頂点からの出次数（出ていく辺の数）がちょうど \(1\) である有向グラフ（Functional Graph）において、指定された頂点から出発して同じ頂点を再び訪れるまでに通る「異なる頂点の数」をすべてのクエリに対して高速に求める問題です。

---

考察

グラフの構造（Functional Graph）

すべての子供が必ず一人の相手にボールを渡すため、このゲームは「すべての頂点の出次数が \(1\) である有向グラフ」とみなせます。このようなグラフは Functional Graph と呼ばれ、以下のような特徴を持ちます。 - グラフはいくつかのグループ（連結成分）に分かれる。 - 各グループは、1つのサイクル（閉路）と、そのサイクルに流れ込む木（パス）から構成される。

ボールが通る人数の規則性

子供 \(S\) からゲームを開始したとき、ボールの軌道はスタート位置によって以下の2パターンに分かれます。

1. スタート地点 \(S\) がサイクルに含まれる場合

   • ボールはサイクルを1周して \(S\) に戻ってきます。
   • このとき、ボールを受け取る人数は「サイクルの長さ（頂点数）」と等しくなります。
   • 例：長さ \(3\) のサイクル \(1 \to 2 \to 3 \to 1\) があるとき、どこから始めても人数は \(3\) です。

2. スタート地点 \(S\) がサイクルに含まれない場合

   • ボールはサイクル外の木の部分を進み、いずれサイクルへと合流します。
   • サイクルに入った後は、合流地点を起点としてサイクルを1周した時点でゲームが終了します。
   • したがって、受け取る人数は「サイクルに合流するまでの歩数 ＋ 合流したサイクルの長さ」となります。これは、次の移動先を \(T_S\) とすると、\((\text{子供 } T_S \text{ から始めたときの人数}) + 1\) と言い換えることができます。

素朴なアプローチとその限界

各クエリ \(S_j\) に対して毎回シミュレーションを行うと、1回のクエリにつき最悪で \(O(N)\) の時間がかかります。クエリ数が \(Q\) 個あるため、全体の計算量は \(O(NQ)\) となり、 \(N, Q \le 2 \times 10^5\) の制約下では実行時間制限に間に合いません（TLE）。

そのため、「すべての頂点について、そこから始めた場合の答えを事前に \(O(N)\) で計算しておく」というアプローチが必要になります。

---

アルゴリズム

グラフの構造を利用して、以下の手順で各頂点からの答えを事前に計算します。

1. サイクルとそれ以外（木）の分類

入次数（その頂点に流れ込む辺の数）が \(0\) の頂点から順にトポロジカルソートを行います。 - 入次数が \(0\) の頂点をキューに入れます。 - キューから頂点を取り出し、その遷移先の入次数を \(1\) 減らします。新しく入次数が \(0\) になった頂点があればキューに追加します。 - この操作で訪問できた頂点はサイクルに含まれない頂点（木の部分）であり、訪問できなかった頂点はサイクルに含まれる頂点となります。

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

サイクルに含まれる頂点について、まだ探索していない頂点から矢印を辿ることでサイクルを検出します。 - サイクルを \(1\) 周する過程で通った頂点数を数え、そのサイクルに属するすべての頂点 \(u\) に対して ans[u] = (サイクルの長さ) と記録します。

3. サイクル外の頂点の答えを求める

トポロジカルソートで走査した順序（topo_order）を逆順にします。 - 逆順にすることで、サイクルに近い頂点（木の根に近い側）から順に処理することができます。 - 頂点 \(u\) を処理するとき、その遷移先 \(T_u\) の答え ans[T_u] は既に計算済みです。 - したがって、動的計画法（DP）のように ans[u] = ans[T_u] + 1 として、 \(O(1)\) で答えを求めることができます。

4. クエリへの回答

各クエリ \(S_j\) に対して、事前に計算した ans[S_j] を \(O(1)\) で出力します。

---

計算量

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

  • トポロジカルソート、サイクルの検出、逆順でのDPはすべてグラフの頂点数・辺の数に対して線形時間 \(O(N)\) で行えます。
  • 各クエリへの回答は \(O(1)\) なので、全体で \(O(N + Q)\) となり、実行時間制限に余裕で間に合います。

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

  • 遷移先を記録する配列、入次数配列、トポロジカルソート用のキュー、答えを格納する配列などで \(O(N)\) のメモリを使用します。

---

実装のポイント

• トポロジカルソートの逆順の利用: トポロジカルソートは「葉（入次数0）」から「根（サイクルとの合流点）」に向かって進みます。その順序を反転（reverse）させることで、「根」から「葉」の順に探索できるようになり、遷移先の情報が必ず確定した状態でDPの遷移を行うことができます。

• 高速な入出力: C++では \(N, Q\) が大きいため、cin.tie(NULL); ios_base::sync_with_stdio(false); を使用して入出力を高速化することが推奨されます。

  ソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    // 高速な入出力
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    vector<int> T(N + 1);
    vector<int> in_degree(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        cin >> T[i];
        in_degree[T[i]]++;
    }

    // トポロジカルソートにより、サイクルに含まれない頂点を抽出する
    queue<int> que;
    for (int i = 1; i <= N; ++i) {
        if (in_degree[i] == 0) {
            que.push(i);
        }
    }

    vector<int> topo_order;
    vector<bool> is_cycle(N + 1, true);
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        topo_order.push_back(u);
        is_cycle[u] = false;
        int v = T[u];
        in_degree[v]--;
        if (in_degree[v] == 0) {
            que.push(v);
        }
    }

    vector<int> ans(N + 1, 0);
    vector<bool> visited(N + 1, false);

    // サイクルに含まれる頂点について、サイクルの長さを求める
    for (int i = 1; i <= N; ++i) {
        if (is_cycle[i] && !visited[i]) {
            vector<int> cycle_nodes;
            int curr = i;
            while (!visited[curr]) {
                visited[curr] = true;
                cycle_nodes.push_back(curr);
                curr = T[curr];
            }
            int cycle_size = cycle_nodes.size();
            for (int u : cycle_nodes) {
                ans[u] = cycle_size;
            }
        }
    }

    // サイクルに含まれない頂点について、トポロジカルソートの逆順に答えを計算する
    reverse(topo_order.begin(), topo_order.end());
    for (int u : topo_order) {
        ans[u] = ans[T[u]] + 1;
    }

    // 各クエリに対する回答
    for (int q = 0; q < Q; ++q) {
        int S;
        cin >> S;
        cout << ans[S] << "\n";
    }

    return 0;
}

---

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