Blood Cousins Return

题意翻译

给定一片森林，每次询问一个节点的 K-Son 共有个多少不同的名字。一个节点的 K-Son 即为在该节点子树内的，深度是该节点深度加 $K$ 的节点。

题目描述

Polycarpus got hold of a family tree. The found tree describes the family relations of $ n $ people, numbered from 1 to $ n $ . Every person in this tree has at most one direct ancestor. Also, each person in the tree has a name, the names are not necessarily unique. We call the man with a number $ a $ a 1-ancestor of the man with a number $ b $ , if the man with a number $ a $ is a direct ancestor of the man with a number $ b $ . We call the man with a number $ a $ a $ k $ -ancestor $ (k>1) $ of the man with a number $ b $ , if the man with a number $ b $ has a 1-ancestor, and the man with a number $ a $ is a $ (k-1) $ -ancestor of the 1-ancestor of the man with a number $ b $ . In the tree the family ties do not form cycles. In other words there isn't a person who is his own direct or indirect ancestor (that is, who is an $ x $ -ancestor of himself, for some $ x $ , $ x > 0 $ ). We call a man with a number $ a $ the $ k $ -son of the man with a number $ b $ , if the man with a number $ b $ is a $ k $ -ancestor of the man with a number $ a $ . Polycarpus is very much interested in how many sons and which sons each person has. He took a piece of paper and wrote $ m $ pairs of numbers $ v_{i} $ , $ k_{i} $ . Help him to learn for each pair $ v_{i} $ , $ k_{i} $ the number of distinct names among all names of the $ k_{i} $ -sons of the man with number $ v_{i} $ .

输入输出格式

输入格式

The first line of the input contains a single integer $ n $ $ (1 \le n \le 10^{5}) $ — the number of people in the tree. Next $ n $ lines contain the description of people in the tree. The $ i $ -th line contains space-separated string $ s_{i} $ and integer $ r_{i} $ $ (0<=r_{i}<=n) $ , where $ s_{i} $ is the name of the man with a number $ i $ , and $ r_{i} $ is either the number of the direct ancestor of the man with a number $ i $ or 0, if the man with a number $ i $ has no direct ancestor. The next line contains a single integer $ m $ $ (1 \le m \le 10^{5}) $ — the number of Polycarpus's records. Next $ m $ lines contain space-separated pairs of integers. The $ i $ -th line contains integers $ v_{i} $ , $ k_{i} $ $ (1 \le v_{i},k_{i} \le n) $ . It is guaranteed that the family relationships do not form cycles. The names of all people are non-empty strings, consisting of no more than $20$ lowercase English letters.

输出格式

Print $ m $ whitespace-separated integers — the answers to Polycarpus's records. Print the answers to the records in the order, in which the records occur in the input.

输入输出样例

输入样例 #1

6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1

输出样例 #1

2
2
0
1
0

输入样例 #2

6
valera 0
valera 1
valera 1
gerald 0
valera 4
kolya 4
7
1 1
1 2
2 1
2 2
4 1
5 1
6 1

输出样例 #2

1
0
0
0
2
0
0