## SGS Programming Challenge P5 - Tree After School

View as PDF

Points: 20 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type

After a long day at school, Andy went home to visit his favourite tree.

This tree will grow every day. Let's call the tree on day . The initial tree is , which consists of nodes. Every day, each leaf node will be replaced with a subtree identical to .

Nodes in the tree will be given indices based on their preorder traversal. Note that the tree given is not necessarily a binary tree.

For example, the following graph shows a possible tree , followed by , and followed by an illustration of how nodes in would be ordered according to its preorder traversal:

This tree has already been growing for days, meaning the current tree is . Andy will ask you queries about the length of the simple path between some pair of nodes and .

Recall a simple path is a path that does not have repeating vertices.

#### Input Specification

The first line contains an integer , the initial number of nodes in the tree.

The second line contains integers. The integer is the father of node in . The tree will always be rooted on node . The indices of the nodes given in input are the indices according to the preorder traversal in . It is guaranteed that the indices given in input form a valid preorder traversal in .

The third line contains two integers and . means the tree has been growing for days, and means the number of queries Andy will ask.

The following lines contain two integers and , meaning Andy wishes to know the length of the simple path between node and .

#### Output Specification

For each of the queries, output each answer on one line.

#### Sample Input 1

10
1 2 3 4 4 3 3 3 2
0 5
1 5
2 9
5 8
2 6
2 10

#### Sample Output 1

4
2
3
3
1

#### Sample Explanation 1

This is the tree formed:

#### Sample Input 2

10
1 2 3 4 4 3 3 3 2
2 5
10 20
15 16
89 99
12 98
100 1

#### Sample Output 2

4
2
9
16
10