已AC非主席树，求证明正确性

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 5;
struct Op {
	int ver, pos, val;
};
Op ops[N]; // 记录操作，用于回溯
int n, m, a[N], fa[N]; // fa 并查集，快速回溯

int find(int tv, int pos) {
	int cur = tv;
	while (1) {
		if (ops[cur].pos == pos) return cur;
		if (cur == 0) return 0;
		
		// 路径压缩
		if (fa[cur] != cur && fa[cur] != 0) {
			cur = fa[cur];  // 跳转到已缓存的答案
		} else {
			cur = ops[cur].ver;  // 向上回溯
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	
	for (int i = 1; i <= n; i++)
		cin >> a[i];

	ops[0] = {0, 0, 0};
	fa[0] = 0;

	for (int i = 1; i <= m; i++) {
		int v, op, p;
		cin >> v >> op >> p;

		if (op == 1) {
			int c;
			cin >> c;
			ops[i] = {v, p, c};
			fa[i] = i; // 直接修改
		} else {
			int fver = find(v, p);
			int ans = (fver == 0) ? a[p] : ops[fver].val;
			cout << ans << endl;
			ops[i] = ops[v];
			fa[i] = fver; // 记录
		}
	}
	return 0;
}