Hard Data Structures > Disjoined Set

Ohani has recently learned a data structure, named - Link Cut Tree. But she is not able to do the code correctly. She tried a lot, but always she fails. As a result, she is here to take help from you. She is giving you the problem to solve. As you are a genius programmer, you have to help Ohani. You will be given a weighted tree, rooted from node 1. And there will be two types of task: 1. You will be given a node U. You have to delete the edge between the parent of U and itself. As a result, there will be a new tree whose root will be U. 2. You will be given a node U. You have to say, which node is the parent of the tree that contains U, and you have to find the total cost of the path from U to the root of that tree. Input: ------ The first line of the input will contain a number N. The next line will contain N-1 numbers. The i-th number will represent the parent of the node labeled with (i+1). The next line will contain N-1 numbers. The i-th number will represent the weight of the edge between (i+1)-th node & parent of (i+1)-th node. The next line will contain a number Q, representing the number of queries. Each of the next Q lines will contain two numbers - X Y. Y will be always represent a node labeled with Y. If X = 1, then you have to delete the edge between Y and its parent. If X = 2, then you have to find the root of the tree containing Y and the weight of the path from Y to its root. All the queries will be always valid. Constraints: -------------- 1 <= N <= 100000 2 <= par[i+1] <= 100000 1 <= weight[i+1] <= 100000 1 <= X <= 2 1 <= Y <= N when X = 2 2 <= Y <= N when X = 1 Output: ------- For each query of type - 2, you have to print two integers on each line - P W. P will be the root, and W will be the total weight of path from Y to P. Sample Input ------------ 5 1 2 3 4 10 10 10 10 3 2 3 1 3 2 3 Sample Output ------------- 1 20 3 0

Raihat Zaman