分数: 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第次查询,没有顶点满足条件。
