SGS Programming Challenge P5 - Tree After School

View as PDF

Submit solution

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 T_x the tree on day x. The initial tree is T_0, which consists of N nodes. Every day, each leaf node will be replaced with a subtree identical to T_0.

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 T_0, followed by T_1, and followed by an illustration of how nodes in T_1 would be ordered according to its preorder traversal:

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

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


For all subtasks:

2 \le N \le 10^5

1 \le Q \le 10^5

0 \le K \le 10^9

1 \le u, v \le 10^9

Subtask 1 [10%]

K = 0

Subtask 2 [60%]

K \le 30

Subtask 3 [30%]

No additional constraints.

Input Specification

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

The second line contains N-1 integers. The i^\text{th} integer is the father of node i+1 in T_0. The tree will always be rooted on node 1. The indices of the nodes given in input are the indices according to the preorder traversal in T_0. It is guaranteed that the indices given in input form a valid preorder traversal in T_0.

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

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

Output Specification

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

Sample Input 1

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

Sample Output 1


Sample Explanation 1

This is the tree formed:

Sample Input 2

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

Sample Output 2



There are no comments at the moment.