DCP-150: Ohani And The Link Cut Tree Back to All Problems

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


Problem Setter:

Raihat Zaman

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 3.00
Go 3.00
Java 3.00
JavaScript 3.00
Objective-C 3.00
Perl 3.00
PHP 3.00
Python 3.00
Python3 3.00
Ruby 3.00
VB.Net 3.00

Problem Stats

13/60

Solve/Submission

Ranking

# User Language Timing
01 feodorv C 0.07s
02 Morass Cpp14 0.08s
03 seyedssz Cpp14 0.10s
04 INUA Cpp14 0.17s
05 kazinayeem Cpp14 0.46s
06 raihatneloy Cpp14 0.55s
07 khatribiru Cpp14 0.61s
08 sahedsohel Cpp14 0.68s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support