Preparing NOJ

Polycarpus got hold of a family relationship tree. The tree describes family relationships of *n* people, numbered 1 through *n*. Each person in the tree has no more than one parent.

Let's call person *a* a 1-ancestor of person *b*, if *a* is the parent of *b*.

Let's call person *a* a *k*-ancestor (*k* > 1) of person *b*, if person *b* has a 1-ancestor, and *a* is a (*k* - 1)-ancestor of *b*'s 1-ancestor.

Family relationships don't form cycles in the found tree. In other words, there is no person who is his own ancestor, directly or indirectly (that is, who is an *x*-ancestor for himself, for some *x*, *x* > 0).

Let's call two people *x* and *y* (*x* ≠ *y*) *p*-th cousins (*p* > 0), if there is person *z*, who is a *p*-ancestor of *x* and a *p*-ancestor of *y*.

Polycarpus wonders how many counsins and what kinds of them everybody has. He took a piece of paper and wrote *m* pairs of integers *v*_{i}, *p*_{i}. Help him to calculate the number of *p*_{i}-th cousins that person *v*_{i} has, for each pair *v*_{i}, *p*_{i}.

The first input line contains a single integer *n* (1 ≤ *n* ≤ 10^{5}) — the number of people in the tree. The next line contains *n* space-separated integers *r*_{1}, *r*_{2}, ..., *r*_{n}, where *r*_{i} (1 ≤ *r*_{i} ≤ *n*) is the number of person *i*'s parent or 0, if person *i* has no parent. It is guaranteed that family relationships don't form cycles.

The third line contains a single number *m* (1 ≤ *m* ≤ 10^{5}) — the number of family relationship queries Polycarus has. Next *m* lines contain pairs of space-separated integers. The *i*-th line contains numbers *v*_{i}, *p*_{i} (1 ≤ *v*_{i}, *p*_{i} ≤ *n*).

Print *m* space-separated integers — the answers to Polycarpus' queries. Print the answers to the queries in the order, in which the queries occur in the input.

6

0 1 1 0 4 4

7

1 1

1 2

2 1

2 2

4 1

5 1

6 1

0 0 1 0 0 1 1

Info

Provider CodeForces

Origin Codeforces Round #130 (Div. 2)

Code CF208E

Tags

binary searchdata structuresdfs and similartrees

Submitted 11

Passed 9

AC Rate 81.82%

Date 03/03/2019 21:05:13

Related