\(G\) の強連結成分分解を考えます。

上図において、黒い辺は \(G_S\) 由来の辺を、赤い辺はクエリで追加された辺を表しています。また、頂点に書かれた数字は、同じ数字が書かれた頂点が同じ強連結成分に属していることを表します。

\(G\) において黒い辺だけを取り出したときにできる有向木のことを、以降黒い木とよびます。

出力クエリ (\(2\) 番目の形式のクエリ) について考えてみましょう。上図のように、各強連結成分は黒い木上の部分木になっているので、「黒い辺を辿ると頂点番号が必ず増加する」という本問題の設定上、頂点 \(x\) を含む強連結成分の外を探すことは無意味です (頂点 \(x\) を含む強連結成分の外であって \(x\) から到達可能な範囲には、頂点番号が \(x\) より大きい頂点しか存在しないため)。よって、「頂点 \(x\) を含む強連結成分内で最も番号が小さい頂点」が出力クエリの答えになります。

辺追加クエリ (\(1\) 番目の形式のクエリ) について考えてみましょう。黒い木上で \(v\) から \(u\) に伸びるパスを \(P\) として、\(P\) と共通部分を持つような強連結成分の集合を \(S\) とすると、\(u \rightarrow v\) の辺を追加することで \(S\) 全体が新たに \(1\) つの強連結成分になります。

よって、強連結成分を Union-Find で管理しながら、各強連結成分について「その強連結成分内にある頂点の番号の最小値」\(\dots(*)\) を持てばよいです。辺追加クエリにおいては、上述した \(S\) を \(|S|\) 程度で求める必要があります (つまり、\(|P|\) かかってはいけない) が、これは \((*)\) の値をうまく利用することで実現できます。詳しくは下記の実装例をご参照ください。

想定解 (C++) :

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        --p[i];
    }
    
    dsu uf(n);
    vector<int> r(n); // r[i] = i を代表元とする強連結成分内の最小頂点
    iota(r.begin(), r.end(), 0);
    auto get_min = [&](int i) { return r[uf.leader(i)]; }; // i を含む強連結成分内の最小頂点
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            while (get_min(u) > v) {
                int mn = get_min(u);
                int nr = get_min(p[mn]);
                r[uf.merge(mn, p[mn])] = nr;
            }
        } else {
            int x;
            cin >> x;
            --x;
            cout << get_min(x) + 1 << '\n';
        }
    }
}