AT_abc202_e [ABC202E] Count Descendants

题目描述

有一棵包含 $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$ 个查询的答案。

输入输出样例 #1

输入 #1

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

输出 #1

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$
• 所有输入均为整数。

样例解释 1

对于第 $1$ 个查询，顶点 $4, 5, 7$ 满足条件。对于第 $2$ 个查询，只有顶点 $7$ 满足条件。对于第 $3$、$4$ 个查询，没有顶点满足条件。

由 ChatGPT 4.1 翻译