Perform a Depth-First search (DFS) from the root and record the timestamp when entering a vertex, \(\mathrm{in}_u\), and when exitting a vertex, \(\mathrm{out}_u\). For the Sample Input, it will be as follows:

Here, the following property is important:

• \(x\) is a descendant of \(y\) \(\Leftrightarrow \mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\).

Here, \(x\) is said to be a descendant of \(y\) if and only if the shortest path from the root to \(x\) contains \(y\).

That “\(x\) is a descendant of \(y\) \(\Leftrightarrow \mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\)” is obvious by the progression of DFS; if \(x\) is a descendant of \(y\), then it enters \(x\) after entering \(y\), and exits \(x\) before exiting \(y\). Therefore, it is sufficient to show “\(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\) \(\Rightarrow\) \(x\) is a descendant of \(y\)”.

We will show the contraposition. Assume that \(x\) is not a descendant of \(y\). If \(y\) is a descendant of \(x\), then \(\mathrm{in}_x \leq \mathrm{in}_y < \mathrm{out}_x\), and since \(x \neq y\), \(\mathrm{in}_x \neq \mathrm{in}_y\), so we can see that “it does not hold that \(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\).” Now we also assume that \(y\) is not a descendant of \(x\).

Let \(z\) be the lowest common ancestor (LCA) of \(x\) and \(y\). By the assumption, \(x \neq z\) and \(y \neq z\).

Let \(c_x\) be a child of \(z\) such that its subtree contains \(x\), and let us define \(c_y\) similarly. Here, \(c_x \neq c_y\); if \(c_x = c_y\), it contradicts to the fact \(z\) is the LCA.

Considering the progression of the DFS, we can see that one of the following holds:

• \(\mathrm{in}_{c_x} < \mathrm{out}_{c_x} < \mathrm{in}_{c_y} < \mathrm{out}_{c_y}\)
• \(\mathrm{in}_{c_y} < \mathrm{out}_{c_y} < \mathrm{in}_{c_x} < \mathrm{out}_{c_x}\)

In any case, \([\mathrm{in}_x, \mathrm{out}_x]\) and \([\mathrm{in}_y, \mathrm{out}_y]\) have nothing in common, since \(x\) is a descendant of \(c_x\) and \(y\) is a descendant of \(c_y\). Therefore, we have shown that it does not hold that \(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\).

The proof above can be understood intuitively by considering the rooted tree as a parenthesis sequence.

This problem can be solved easily by applying the property we proved. For each depth, record the values of \(\mathrm{in}\) of vertices of that depth. For a query \((U, D)\), it is sufficient to answer the number of such elements associated with depth \(D\) that is more than or equal to \( \mathrm{in}_U\), and less than \(\mathrm{out}_U\). This can be accomplished by binary search. In C++, we can use a function such as std::lower_bound.

Sample Code (C++):

#include <iostream>
#include <vector>
#include <algorithm>

std::vector<std::vector<int>> children, list;
std::vector<int> in, out, depth;
int timer;

void dfs(const int u) {
    in[u] = timer++;
    list[depth[u]].push_back(in[u]);
    for (const int v : children[u]) {
        depth[v] = depth[u] + 1;
        dfs(v);
    }
    out[u] = timer++;
}

int main() {
    int N;
    std::cin >> N;
    children = list = std::vector<std::vector<int>>(N);
    in = out = depth = std::vector<int>(N);
    for (int i = 1; i < N; ++i) {
        int p;
        std::cin >> p;
        children[p - 1].push_back(i);
    }
    dfs(0);
    int Q;
    std::cin >> Q;
    while (Q--) {
        int u, d;
        std::cin >> u >> d;
        u -= 1;
        const auto& v = list[d];
        std::cout << std::lower_bound(v.cbegin(), v.cend(), out[u]) - std::lower_bound(v.cbegin(), v.cend(), in[u]) << '\n';
    }
    return 0;
}