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_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

提示

$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$ 个查询中，顶点 $4$, $5$ 和 $7$ 满足条件。 在第 $2$ 个查询中，只有顶点 $7$ 满足条件。 在第 $3$ 和第 $4$ 个查询中，没有顶点满足条件。

标签: AtCoder|abc202E

来源

AtCoder|abc202E