Problem 1

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

#define ll long long
#define ar array

const int mxN=2e5;
int n, a[mxN], q, qt, qi, qj, d[mxN], anc[mxN][18];
ar<int, 2> st[1<<19];

//is a anc of b
bool ia(int a, int b) {
    int dd=d[b]-d[a];
    for(int i=17; i>=0; --i) {
        if(dd>=1<<i) {
            b=anc[b][i];
            dd-=1<<i;
        }
    }
    return a==b;
}

int lca(int a, int b) {
    if(d[a]>d[b])
        swap(a, b);
    int dd=d[b]-d[a];
    for(int i=17; i>=0; --i) {
        if(dd>=1<<i) {
            b=anc[b][i];
            dd-=1<<i;
        }
    }
    if(a==b)
        return a;
    for(int i=17; i>=0; --i) {
        if(anc[a][i]!=anc[b][i]) {
            a=anc[a][i];
            b=anc[b][i];
        }
    }
    return anc[a][0];
}

void cmb(ar<int, 2> &a, int b) {
    if(b==-1||a[0]==-1) {
        a[0]=a[1]=-1;
        return;
    }
    if(d[a[0]]<d[a[1]])
        swap(a[0], a[1]);
    //d[a[0]] > d[a[1]]
    if(ia(a[1], a[0])) {
        if(d[a[1]]<=d[b]&&d[b]<=d[a[0]]&&ia(b, a[0]))
            return;
        if(ia(a[0], b)) {
            a[0]=b;
            return;
        }
        int c=lca(a[0], b);
        if(d[c]>d[a[1]]) {
            a[0]=a[1]=-1;
            return;
        }
        a[1]=b;
        return;
    } else {
        if(ia(a[0], b)) {
            a[0]=b;
            return;
        }
        if(ia(a[1], b)) {
            a[1]=b;
            return;
        }
        int c=lca(a[0], a[1]);
        if(d[b]>=d[c]&&(ia(b, a[0])||ia(b, a[1])))
            return;
        a[0]=a[1]=-1;
        return;
    }
}

ar<int, 2> cmb2(ar<int, 2> a, ar<int, 2> b) {
    cmb(a, b[0]);
    cmb(a, b[1]);
    return a;
}

void upd(int l1, ar<int, 2> x, int i=1, int l2=0, int r2=n-1) {
    if(l2==r2) {
        st[i]=x;
        return;
    }
    int m2=(l2+r2)/2;
    if(l1<=m2)
        upd(l1, x, 2*i, l2, m2);
    else
        upd(l1, x, 2*i+1, m2+1, r2);
    st[i]=cmb2(st[2*i], st[2*i+1]);
//  cout << i << " " << st[i][0] << " " << st[i][1] << endl;
}

int qry(int i=1, int l2=0, int r2=n-1, ar<int, 2> p={}) {
    ar<int, 2> a=st[i];
    if(l2)
        a=cmb2(a, p);
    if(a[0]!=-1)
        return r2+1;
    if(l2==r2)
        return l2;
    int m2=(l2+r2)/2;
    ar<int, 2> b=st[2*i];
    if(l2)
        b=cmb2(b, p);
    if(b[0]!=-1)
        return qry(2*i+1, m2+1, r2, b);
    return qry(2*i, l2, m2, p);
}

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

    cin >> n;
    for(int i=0; i<n; ++i)
        cin >> a[i];
    memset(anc[0], -1, sizeof(anc[0]));
    for(int i=1; i<n; ++i) {
        cin >> anc[i][0], --anc[i][0];
        d[i]=d[anc[i][0]]+1;
        for(int j=1; j<18; ++j)
            anc[i][j]=anc[i][j-1]==-1?-1:anc[anc[i][j-1]][j-1];
    }
    for(int i=0; i<n; ++i)
        upd(a[i], {i, i});
    ar<int, 2> b=cmb2({0, 0}, {2, 2});
//  cout << b[0] << " " << b[1] << endl;
    cin >> q;
    while(q--) {
        cin >> qt;
        if(qt==1) {
            cin >> qi >> qj, --qi, --qj;
            swap(a[qi], a[qj]);
            upd(a[qi], {qi, qi});
            upd(a[qj], {qj, qj});
        } else
            cout << qry() << "\n";
    }
}