SAMBOX - Samvel and Boxes
King of Boxes Robert wants to test Samvel. He has given Samvel n boxes indexed from 1 to n. All the boxes except the first one are located in another box. Robert wants to fill the boxes with apples (At beginning boxes contain no apples). Robert can ask Samvel queries of 4 types.
The queries are
1) Robert says two integers x,y to Samvel. Samvel needs to add x (1≤x≤10^9) apples to the y-th box. (1≤y≤n)
2) Robert says two integers x,y to Samvel. Samvel needs to swap the indexes of the x-th and y-th boxes. (1≤x,y≤n)
3) Robert says an integer x to Samvel. Samvel needs to say the number of apples located in the box x (1≤x≤n) and in the boxes that are in the box x (directly or indirectly).
4) Robert says an integer x to Samvel. Samvel needs to answer the querie of the third type for the box that has minimum index from the boxes that are located directly in the box x. (1≤x≤n)
Samvel needs your help. help him and write a program to answer this queries.
The first line of input contains an integer n (2≤n≤10^5) and q (1≤q≤10^5), number of boxes and number of queries.
Second line contains n-1 integers a1...an-1. ai-1 is the index of the box that contains box i. (1≤ai≤n)
The lines from 3 to q+2 contain an integer k (type of the querie). if k=1 or k=2 then goes the two integer x,y from the task, else there is only one integer x.
For each querie of type 3 or 4 you need to output one integer the answer of querie in a seperate line. If query type is 4 and given box has no oher boxes in it print -1.
Input: 4 6 1 1 2 1 5 1 3 1 2 1 3 3 3 1 60 1 4 3
Output: 5 5 60
Very good problem!!!
Thank you for this beautiful and educational problem.
I am very sorry for 1 wrong test case. Please resubmit your solutions.
I've made the following assumption: