配点 : $500$ 点

問題文

$N$ 頂点の根付き木があり、頂点は $1, 2, \dots, N$ と番号付けられています。

頂点 $1$ が根であり、頂点 $i \, (2 \leq i \leq N)$ の親は $P_i$ です。

$Q$ 個のクエリが与えられます。$i \, (1 \leq i \leq Q)$ 番目のクエリでは、整数 $U_i, D_i$ が与えられるので、次の条件を全て満たす頂点 $u$ の個数を求めてください。

• $u$ から根への最短パス上（端点も含む）に頂点 $U_i$ が存在する。
• $u$ から根への最短パスに含まれる辺の数がちょうど $D_i$ である。

制約

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq P_i < i$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_i \leq N$
• $0 \leq D_i \leq N - 1$
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$P_2$ $P_3$ $\ldots$ $P_N$

$Q$

$U_1$ $D_1$

$U_2$ $D_2$

$\vdots$

$U_Q$ $D_Q$

出力

$Q$ 行出力せよ。 $i$ 行目には $i$ 番目のクエリに対する答えを出力せよ。

7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5

3
1
0
0

$1$ 番目のクエリでは、頂点 $4, 5, 7$ が条件を満たします。 $2$ 番目のクエリでは、頂点 $7$ のみが条件を満たします。 $3$ 番目、$4$ 番目のクエリでは、条件を満たす頂点は存在しません。