不难发现初始图 \(G_S\) 就是一棵树，边的方向由父亲到儿子。那么在进行连边操作之前，每个节点能到达的编号最小的节点就是其子树中编号最小的节点。又因为题目里的连边操作都是从小编号连到大编号的，所以每个节点子树中编号最小的节点就是它本身。
观察连边操作的限制：
- \(u\neq v\)
- 保证在连这条边之前，存在一条由 \(v\) 到 \(u\) 的路径。
显然由于第二条限制，每次连边必然出环，也就必然出现强连通分量，强连通分量里任意两点可以相互到达，所以询问时就找强连通分量里编号最小的点。由于连的一定是返租边，所以用并查集维护强连通，合并时暴力往上跳即可。感性理解或者势能分析一下都能发现均摊复杂度（应该）是 \(O(n\alpha(n))\) 的。
代码：
#include<bits/stdc++.h>
#define endl '\n'
#define rep(i, s, e) for(int i = s, i##E = e; i <= i##E; ++i)
#define per(i, s, e) for(int i = s, i##E = e; i >= i##E; --i)
#define F first
#define S second
//#define int ll
#define gmin(x, y) ((x > y) && (x = y))
#define gmax(x, y) ((x < y) && (x = y))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double f128;
typedef pair<int, int> pii;
constexpr int N = 2e5 + 5;
int n, q, pa[N], fa[N];
int find(int x) {
return fa[x] == x ? x : fa[x] = find(fa[x]);
}
vector<int> to[N];
signed main() {
#ifdef ONLINE_JUDGE
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
#endif
cin >> n;
rep(i, 1, n - 1) {
int x; cin >> x;
pa[i + 1] = x;
to[x].push_back(i + 1);
}
iota(fa + 1, fa + n + 1, 1);
cin >> q;
while(q--) {
int op; cin >> op;
if(op == 1) {
int x, y; cin >> x >> y;
y = find(y);
for(int i = x; i != y; i = pa[i]) {
i = find(i);
if(i == y) break;
fa[i] = y;
}
}
else {
int x; cin >> x;
cout << find(x) << endl;
}
}
return 0;
}