调了好久了，没有调出来，求 hack。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 500001
const int BASE(7114629);
typedef unsigned long long ull;

int n, m, q;
int a[MAXN], fa[MAXN], dep[MAXN];
ull fp[MAXN], ha[MAXN];
vector<int> e[MAXN]; map<ull, int> mp;

void dfs(int x, ull h){
	mp[ha[x]=h] = x; dep[x] = dep[fa[x]]+1;
	for (int i(0); i<e[x].size(); ++i) dfs(e[x][i], h*BASE+(i+1));
}

namespace Seg{
	struct Node{int len; ull sum;}tr[MAXN<<2];
	Node merge(Node a, Node b){return {a.len+b.len, a.sum*fp[b.len]+b.sum};}
#define push_up(p) tr[p] = merge(tr[p<<1], tr[p<<1|1])
	void build(int p, int l, int r){
		if (l == r){tr[p].len=1; tr[p].sum=a[l]; return;}
		int mid((l+r)>>1);
		build(p<<1, l, mid); build(p<<1|1, mid+1, r);
		push_up(p);
	}
	void modify(int p, int l, int r, int x, int k){
		if (l == r){tr[p].sum=k; return;}
		int mid((l+r)>>1);
		if (x <= mid) modify(p<<1, l, mid, x, k);
		else modify(p<<1|1, mid+1, r, x, k);
		push_up(p);
	}
	Node query(int p, int l, int r, int L, int R){
		if (L <= l && r <= R) return tr[p];
		int mid((l+r)>>1); Node nd{0, 0};
		if (L <= mid) nd = merge(nd, query(p<<1, l, mid, L, R));
		if (R > mid) nd = merge(nd, query(p<<1|1, mid+1, r, L, R));
		return nd;
	}
}

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

	cin >> n >> m >> q;
	for (int i(1); i<=n; ++i){cin >> fa[i]; e[fa[i]].push_back(i);}
	for (int i(1); i<=m; ++i) cin >> a[i];
	fp[0] = 1; for (int i(1); i<=n; ++i) fp[i] = fp[i-1] * BASE;
	dfs(1, 0); Seg::build(1, 1, m);

	for (int opt, x, y, z; q; --q){
		cin >> opt >> x >> y;
		if (opt == 1){
			cin >> z;
			if (e[x].size() < a[y]){cout << x << '\n'; continue;}
			int l(y), r(z), mid;
			while (l < r){
				mid = (l+r+1) >> 1;
				if (mp.count(Seg::query(1, 1, m, y, mid).sum+ha[x]*fp[mid-y+1])) l = mid;
				else r = mid-1;
			}
			cout << mp[Seg::query(1, 1, m, y, l).sum+ha[x]*fp[l-y+1]] << '\n';
		}else Seg::modify(1, 1, m, x, y), a[x] = y;
	}

	return 0;
}