E. Cutting Tree
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: E – Cutting Tree
The first query (C x) is the reverse operation of disjoint set data structure; disjoint set data structure supports a query to merge two sets into one, but in this problem, you’re asked to do the reverse operation. Should we invent a new data structure to solve this problem? Fortunately, no. This problem can be solved by the same disjoint set data structure, you only need one clever trick.
Notice that even though the problem appears to ask you to answer the query in an online fashion, but all the inputs are given to you at once (batch), thus, this problem can be solved with an offline method. By online I mean: process each input one by one in the given order (you don’t know the future input), on the other hand, offline means all the inputs are given at the beginning, thus you might not need to predict/prepare for the future as you already have all the needed data. Many problems in programming contest in this form can be solved by “cleverly” read all the inputs first before doing any computation.
So, what is the trick for this problem? REVERSE the query order. If you do this, then the first query, “disconnect x from its parent”, become “join x with another node”. An exact query which can be answered by the disjoint set data structure. Therefore, you only need to answer each query in the reversed order (store the output), and then reverse the (stored) output before dumping it to the real output.
However, you should be carefull in handling the statement “If node x has no parent, then ignore this query”. This statament also implies that C x can appear more than once in the input, only the first one has effect (you should note this when reversing the query order).