算法分析

可以考虑用并查集来维护强连通分量，而操作 $2$ 的答案就是点 $x$ 所在小组中的最小编号

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;

    vector<int> p(n, -1);
    rep(i, n-1) {
        cin >> p[i+1];
        p[i+1]--;
    }

    dsu uf(n);
    vector<int> root(n);
    rep(i, n) root[i] = i;
    auto get = [&](int v) -> int& {
        return root[uf.leader(v)];
    };
    auto merge = [&](int a, int b) {
        int r = min(get(a), get(b));
        uf.merge(a, b);
        get(a) = r;
    };

    int q;
    cin >> q;
    rep(qi, q) {
        int type;
        cin >> type;
        if (type == 1) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            while (!uf.same(u, v)) {
                u = get(u);
                merge(u, p[u]);
            }
        }
        else {
            int x;
            cin >> x;
            --x;
            int ans = get(x)+1;
            cout << ans << '\n';
        }
    }

    return 0;
}