题目描述

$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$ である。

输入格式

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

$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$ 番目のクエリに対する答えを出力せよ。

题目大意

• 给出一个 $n$ 个点的有根树，节点编号为 $1, 2, \cdots n$，树根为 $1$，第 $i$（$2 \le i \le n$）号节点的父亲是 $p_i$。

• 给出 $q$ 个查询，第 $i$ 个查询包含 $a_i, b_i$，计算满足以下条件的点 $u$ 的个数：

  1. $a_i$ 位于 $u$ 到 $1$ 的最短路径上（端点也算）；

  2. $u$ 到根上的路径恰好有 $b_i$ 条边。

• $n, q \le 2 \times 10^5, 0 \le b_i < n$。

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

3
1
0
0

提示

制約

• $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$
• 入力は全て整数である。

Sample Explanation 1

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