← 返回题目列表

AtCoder · abc202_e

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 到根(包括端点)。
  • 有 正是 D_i 的最短路径中的边 u 到根。

约束

  • 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-th 行应包含对 i第一个查询。


示例输入 1

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

示例输出 1

3
1
0
0

在 1-st 查询,顶点 4, 5,和 7 满足条件。 在 2-nd 查询,仅限顶点 7 满足条件。 在 3-rd 和 4第次查询,没有顶点满足条件。

sample