CF246E Blood Cousins Return

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} $ .

N/A

N/A