3646: Blood Cousins Return
[Creator : ]
Description
Polycarpus got hold of a family tree. The found tree describes the family relations ofnpeople, numbered from 1 ton. 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 wrotempairs of numbersvi,ki. 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$.
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 wrotempairs of numbersvi,ki. 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$.
Input
The first line of the input contains a single integer $n\ (1≤n≤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≤m≤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≤v_i,k_i≤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.
The next line contains a single integer $m\ (1≤m≤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≤v_i,k_i≤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.
Output
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.
Sample 1 Input
6
pasha 0
gerald 1
gerald 1
valera 2
igor 3
olesya 1
5
1 1
1 2
1 3
3 1
6 1
Sample 1 Output
2
2
0
1
0
Sample 2 Input
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
Sample 2 Output
1
0
0
0
2
0
0