时空 $O(n)$，4.69s，65.01MB。

$k$ 级祖先，离线下来，把询问挂到点上，用栈求。

区间数 $x$，离线下来拆询问，拆成前缀数 $x$。

然后把拆下来的询问挂到 DFS 序列上，桶维护扫描线。

这个应该是不用卡空间的，但我最开始写了倍增，所以复用了好几个数组。

#include <cstdio>
#include <cstring>
struct E
{
    int v, i, t;
} e[2000001];
struct Q
{
    int p, i, t;
} q[1000001];
int n, m, c, b[1000001], s[1000001], d[1000001], h[1000001], H[1000001], S[1000001];
void A(int u, int v, int i)
{
    e[++c] = {v, i, h[u]};
    h[u] = c;
}
void P(int u, int p, int i)
{
    q[++c] = {p, i, H[u]};
    H[u] = c;
}
void D1(int u)
{
    s[u] = 1;
    b[u] = ++c;
    for (int i = h[u], v; i; i = e[i].t)
        d[v = e[i].v] = d[u] + 1, D1(v), s[u] += s[v];
}
void D2(int u)
{
    S[++c] = u;
    for (int i = H[u]; i; i = q[i].t)
        q[i].p = c > q[i].p ? S[c - q[i].p] : 0;
    for (int i = h[u]; i; i = e[i].t)
        D2(e[i].v);
    --c;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 2, x; i <= n; ++i)
        scanf("%d", &x), A(x, i, 0);
    c = 0;
    D1(d[1] = 1);
    for (int i = c = 0, v, p; i < m; ++i)
        scanf("%d%d", &v, &p), P(v, p, i);
    c = 0;
    D2(1);
    memset(h, c = 0, sizeof h);
    for (int u = 1; u <= n; ++u)
        for (int i = H[u], v; i; i = q[i].t)
            if (v = q[i].p)
                A(b[v] - 1, d[u], q[i].i), A(b[v] + s[v] - 1, d[u], q[i].i);
    for (int i = 1; i <= n; ++i)
        H[b[i]] = d[i];
    memset(b, 0, sizeof b);
    memset(s, 0, sizeof s);
    memset(d, 0, sizeof d);
    for (int u = 0; u <= n; ++u)
    {
        if (u)
            ++d[H[u]];
        for (int i = h[u]; i; i = e[i].t)
            b[e[i].i] -= !s[e[i].i] - d[e[i].v] * (s[e[i].i] ? 1 : s[e[i].i] = -1);
    }
    for (int i = 0; i < m; ++i)
        printf("%d ", b[i]);
    return 0;
}