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




# User Language Timing
01 vatsalsharma376 Cpp14 0.06s
02 feodorv C 0.07s
03 Morass Cpp14 0.08s
04 seyedssz Cpp14 0.10s
05 swarmonster Cpp14 0.10s
06 fsshakkhor Cpp14 0.11s
07 i_love_nikita_gautam Cpp14 0.13s
08 INUA Cpp14 0.17s
09 Robbinb1993 Cpp14 0.18s
10 Nirjhor Cpp14 0.23s
11 alif_biswas Cpp14 0.34s
12 kazinayeem Cpp14 0.46s
13 raihatneloy Cpp14 0.55s
14 khatribiru Cpp14 0.61s
15 sahedsohel Cpp14 0.68s

Your feedback is our precious!

Or call +88 02 9853138 for support