后代计数

题目描述

我们有一棵 $N$ 个顶点的有根树，顶点编号为 $1, 2, \dots, N$。

顶点 $1$ 是根，顶点 $i$（$2 \le i \le N$）的父节点是顶点 $P_i$。

给定 $Q$ 个查询。在第 $i$ 个查询（$1 \le i \le Q$）中，给定整数 $U_i$ 和 $D_i$，求满足以下所有条件的顶点 $u$ 的个数：

• 顶点 $U_i$ 在从 $u$ 到根的最短路径上（包括端点）。
• 从 $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$ 个查询的答案。

样例

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 个查询中，没有顶点满足条件。

数据范围

• $2 \le N \le 2 \times 10^5$
• $1 \le P_i \lt i$
• $1 \le Q \le 2 \times 10^5$
• $1 \le U_i \le N$
• $0 \le D_i \le N - 1$
• 输入均为整数