根から深さ優先探索 (DFS) を行い、各頂点に入った時刻 \(\mathrm{in}_u\) と出た時刻 \(\mathrm{out}_u\) を記録します。入力例については以下のようになります。

ここで、次が成り立つことが重要です。

• \(x\) が \(y\) の子孫である \(\Leftrightarrow \mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\)

ただし、\(x\) が \(y\) の 子孫であるとは、\(x\) から根への最短パス上に \(y\) が存在することとします。

「\(x\) が \(y\) の 子孫である \(\Rightarrow \mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\)」は、DFS がどのように進行するかを考えれば明らかです。\(x\) が \(y\) の 子孫であるならば、\(x\) には \(y\) よりも後に入り、\(x\) を出た後に \(y\) を抜けます。よって、「\(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\) \(\Rightarrow\) \(x\) が \(y\) の 子孫である」を示せばよいです。

対偶を示します。\(x\) が \(y\) の 子孫でないと仮定します。\(y\) が \(x\) の子孫であったとすると、\(\mathrm{in}_x \leq \mathrm{in}_y < \mathrm{out}_x\) となり、\(x \neq y\) より \(\mathrm{in}_x \neq \mathrm{in}_y\) であるので 「\(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\) でない」ことがわかります。以下では、\(y\) が \(x\) の子孫でないことも仮定します。

\(x, y\) の最小共通祖先 (LCA) を \(z\) とおきます。仮定より \(x \neq z\) かつ \(y \neq z\) です。

\(z\) の子であって、それを根とする部分木に \(x\) が含まれるものを \(c_x\) とおきます。\(y\) についても同様に \(c_y\) を定めます。ここで、\(c_x \neq c_y\) です。仮に \(c_x = c_y\) であったとすると、\(z\) が LCA であることに矛盾します。

DFS がどのように進行するか考えてみると、以下のいずれかが成り立つことが分かります。

• \(\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}\)

いずれの場合も、\(x\) が \(c_x\) の子孫であり、\(y\) が \(c_y\) の子孫であることを踏まえると、二つの区間 \([\mathrm{in}_x, \mathrm{out}_x], [\mathrm{in}_y, \mathrm{out}_y]\) は共通部分を持たないことがわかります。したがって、\(\mathrm{in}_y \leq \mathrm{in}_x < \mathrm{out}_y\) でないことが示せました。

なお、以上の証明は、根付き木を括弧列に対応させて考えると直感的に理解することができます。

示した性質を用いると、容易にこの問題を解くことができます。 深さごとに、その深さの頂点の \(\mathrm{in}\) の値を昇順に保持しておきます。クエリ \((U, D)\) に対しては、深さ \(D\) に関して格納された値のうち、\( \mathrm{in}_U\) 以上 \(\mathrm{out}_U\) 未満の値の個数を答えればよいです。これは二分探索によって実現できます。C++ であれば、std::lower_bound などの関数を用いることができます。

実装例 (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;
}