提交记录

#include<iostream>
#include<algorithm>
const int sz = 2e5 + 10;
struct ST {
    int tree[sz << 2];
    void update(int p, int ln, int rn, int pos) {
        if (ln == rn) return tree[p]++, void();
        int mid = ln + rn >> 1;
        if (pos <= mid) update(p << 1, ln, mid, pos);
        else update(p << 1 | 1, mid + 1, rn, pos);
        tree[p] = tree[p << 1] + tree[p << 1 | 1];
    }
    int query(int p, int ln, int rn, int l, int r) {
        if (ln >= l && rn <= r) return tree[p];
        int mid = ln + rn >> 1, res = 0;
        if (l <= mid) res += query(p << 1, ln, mid, l, r);
        if (r > mid) res += query(p << 1 | 1, mid + 1, rn, l, r);
        return res;
    }
} st;
struct edge {
    int nxt, to;
} graph[sz << 1];
int head[sz], hpp;
void addEdge(int from, int to) {
    graph[++hpp] = edge{head[from], to};
    head[from] = hpp;
}
int dfn[sz], dpp, dep[sz], hson[sz], top[sz], fa[sz], ssz[sz], n, q, rt;
void buildDFS(int u, int fau) {
    dep[u] = dep[fau] + 1, ssz[u] = 1, fa[u] = fau;
    for (int p = head[u]; p; p = graph[p].nxt) {
        int v = graph[p].to;
        if (v == fau) continue;
        buildDFS(v, u);
        ssz[v] += ssz[u];
        if (ssz[v] > ssz[hson[u]]) hson[u] = v;
    }
}
void chainDFS(int u, int t) {
    dfn[u] = ++dpp, top[u] = t;
    if (!hson[u]) return;
    chainDFS(hson[u], t);
    for (int p = head[u]; p; p = graph[p].nxt) {
        int v = graph[p].to;
        if (v == hson[u] || v == fa[u]) continue;
        chainDFS(v, v);
    }
}
struct Query {
    int x, y, c, id;
    bool operator<(const Query &a) const {
        return c < a.c;
    }
} que[sz];
struct Modify {
    int pos, val;
} change[sz];
int qpp, cpp;
std::pair<int, int> ans[sz];
bool vis[sz];
void modify(int pos) {
    if (!vis[pos]) vis[pos] = true, st.update(1, 1, n, dfn[pos]);
}
std::pair<int, int> query(int u, int v) {
    std::pair<int, int> res = std::make_pair(0, 0);
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
        res.first += dfn[top[u]] - dfn[u] + 1;
        res.second += st.query(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) std::swap(u, v);
    res.first += dfn[v] - dfn[u] + 1;
    res.second += st.query(1, 1, n, dfn[u], dfn[v]);
    return res;
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 1, x; i <= n; i++) {
        std::cin >> x;
        if (x == 0) rt = i;
        else addEdge(i, x), addEdge(x, i);
    }
    buildDFS(rt, 0);
    chainDFS(rt, rt);
    std::cin >> q;
    for (int i = 1; i <= q; i++) {
        int op, x, y, z;
        std::cin >> op >> x;
        if (op == 2) change[++cpp] = Modify{x, i};
        else std::cin >> y >> z, que[++qpp] = Query{x, y, i - z - 1, qpp};
    } 
    std::sort(que + 1, que + qpp + 1);
    int tim = 1;
    for (int i = 1; i <= qpp; i++) {
        while (tim <= cpp && change[tim].val <= que[i].c) modify(change[tim++].pos);
        ans[que[i].id] = query(que[i].x, que[i].y);
    }
    for (int i = 1; i <= qpp; i++)
        std::cout << ans[i].first << " " << ans[i].second << "\n";
    return 0;
}