/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 から根への最短パス上（端点も含む）に頂点 U_i が存在する。
- 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 番目のクエリに対する答えを出力せよ。
入力例 1
7 1 1 2 2 4 2 4 1 2 7 2 4 1 5 5
出力例 1
3 1 0 0
1 番目のクエリでは、頂点 4, 5, 7 が条件を満たします。 2 番目のクエリでは、頂点 7 のみが条件を満たします。 3 番目、4 番目のクエリでは、条件を満たす頂点は存在しません。
Score : 500 points
Problem Statement
We have a rooted tree with N vertices, numbered 1, 2, \dots, N.
Vertex 1 is the root, and the parent of Vertex i \, (2 \leq i \leq N) is Vertex P_i.
You are given Q queries. In the i-th query (1 \leq i \leq Q), given integers U_i and D_i, find the number of vertices u that satisfy all of the following conditions:
- Vertex U_i is in the shortest path from u to the root (including the endpoints).
- There are exactly D_i edges in the shortest path from u to the root.
Constraints
- 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
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N P_2 P_3 \ldots P_N Q U_1 D_1 U_2 D_2 \vdots U_Q D_Q
Output
Print Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
7 1 1 2 2 4 2 4 1 2 7 2 4 1 5 5
Sample Output 1
3 1 0 0
In the 1-st query, Vertices 4, 5, and 7 satisfy the conditions. In the 2-nd query, only Vertices 7 satisfies the conditions. In the 3-rd and 4-th queries, no vertice satisfies the conditions.