E - 计算后代数量

分数：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_i$ 在从 $u$ 到根的最短路径上（包括两端点）。
• 从 $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

在第一个查询中，顶点 $4$，$5$ 和 $7$ 满足条件。 在第二个查询中，只有顶点 $7$ 满足条件。 在第三个和第四个查询中，没有顶点满足条件。