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

35/189

Solve/Submission

Ranking

# 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 abrunoaa Cpp14 0.11s
08 i_love_nikita_gautam Cpp14 0.13s
09 sajibreadd Cpp14 0.14s
10 INUA Cpp14 0.17s
11 Robbinb1993 Cpp14 0.18s
12 Nirjhor Cpp14 0.23s
13 _mHm_ Cpp 0.27s
14 alif_biswas Cpp14 0.34s
15 sakib_muhit Cpp 0.35s
16 kazinayeem Cpp14 0.46s
17 raihatneloy Cpp14 0.55s
18 khatribiru Cpp14 0.61s
19 sahedsohel Cpp14 0.68s
20 ajkdrag Java 0.95s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support