好题啊！！！综合考察了多个知识点。

首先一步很显然的转化是：求最大的 $k$ 满足 $[0,k]$ 在一条链上（不要求连续）。
发现这个东西是可以合并的，所以考虑在线段树上维护 $[l,r]$ 是否能在一条链上。
合并的话端点显然只有 $C_4^2=6$ 种可能，直接暴力分讨特判另外两点是否在路径上即可。
至于判断点是否在路径上，直接看点到两端的距离和与路径长度是否相等即可，这里需要求 LCA。

那么这题就简单了，容易想到二分 $k$，用线段树查询 $[0,k]$ 的答案。
看上去是 $O(n \log^2 n)$，实际上还有很多优化空间。

二分改为线段树二分、倍增 LCA 改成欧拉序求 LCA。
于是这题就被优化到了 $O(n \log n)$。

要特判链的情况。

#include <bits/stdc++.h>
#define PII pair<int, int>

using namespace std;
const int N = 5e5 + 15, M = N << 1;
int n, q, rt;
int col[N], id[N];  //每个点的颜色、每个颜色在哪个点
int h[N], e[M], ne[M], idx = 0;
int dep[N], dfn[N];
int up[M][25], lg[M], tot = 0;

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u, int father) {
    up[++tot][0] = u, dfn[u] = tot;
    for (int i = h[u]; ~i; i = ne[i]) {
        int v = e[i];
        if (v == father) continue;
        dep[v] = dep[u] + 1;
        dfs(v, u);
        up[++tot][0] = u;
    }
}

//lca
int get(int u, int v) { return (dep[u] < dep[v]) ? u : v; }
void init() {
    lg[1] = 0;
    for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= tot; j++) {
            if (j + (1 << i) - 1 > tot) break;
            up[j][i] = get(up[j][i - 1], up[j + (1 << i - 1)][i - 1]);
        }
    }
}
int mn(int l, int r) {
    if (l > r) swap(l, r);  //欧拉序可能不保证 l < r
    int len = lg[r - l + 1];
    return get(up[l][len], up[r - (1 << len) + 1][len]);
}
int lca(int u, int v) { return mn(dfn[u], dfn[v]); }
int dis(int u, int v) { return dep[u] + dep[v] - 2 * dep[lca(u, v)]; }

//Segment Tree

bool check(int u, int v, int x) {
    return (dis(u, x) + dis(x, v) == dis(u, v));
}
PII merge(PII x, PII y) {
    if (x.first == -1 || y.first == -1) return make_pair(-1, -1);   //肯定无法组成链
    int a = x.first, b = x.second, c = y.first, d = y.second;
    if (check(a, b, c) && check(a, b, d)) return make_pair(a, b);
    if (check(a, c, b) && check(a, c, d)) return make_pair(a, c);
    if (check(a, d, b) && check(a, d, c)) return make_pair(a, d);
    if (check(b, c, a) && check(b, c, d)) return make_pair(b, c);
    if (check(b, d, a) && check(b, d, c)) return make_pair(b, d);
    if (check(c, d, a) && check(c, d, b)) return make_pair(c, d);
    return make_pair(-1, -1);
}

struct Tree {
    int l, r;
    PII path;    //路径
} tr[N << 2];
void pushup(int u) {
    tr[u].path = merge(tr[u << 1].path, tr[u << 1 | 1].path);
}
void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].path = make_pair(id[l], id[l]);
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
void change(int u, int x, int d) {
    if (tr[u].l == tr[u].r) return tr[u].path = make_pair(d, d), void();
    int mid = tr[u].l + tr[u].r >> 1;
    if (x <= mid) change(u << 1, x, d);
    else change(u << 1 | 1, x, d);
    pushup(u);
}
int query(int u, PII pre) { //线段树二分
    if (tr[u].l == tr[u].r) return tr[u].l;
    int mid = tr[u].l + tr[u].r >> 1;
    PII ls = tr[u << 1].path, nxt;
    if (pre.first == 0 && pre.second == 0) nxt = ls;
    else nxt = merge(pre, ls);
    if (nxt.first == -1) return query(u << 1, pre);
    else return query(u << 1 | 1, nxt);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) h[i] = -1;
    for (int i = 1; i <= n; i++) scanf("%d", &col[i]), id[col[i]] = i;
    bool flag = 1;
    for (int i = 2, fa; i <= n; i++) {
        scanf("%d", &fa);
        flag &= (fa == i - 1);
        add(fa, i), add(i, fa);
    }
    dfs(1, 0), init();
    build(1, 0, n - 1);
    scanf("%d", &q);
    while (q--) {
        int opt; scanf("%d", &opt);
        if (opt == 1) {
            int u, v; scanf("%d%d", &u, &v);
            if (flag) continue;
            change(1, col[u], v), change(1, col[v], u);
            swap(col[u], col[v]);
        } else {
            if (flag) printf("%d\n", n);
            else printf("%d\n", query(1, make_pair(0, 0)));
        }
    }
    return 0;
}