Problem D : Glass Stepping Stones
SETTER : lamda_cdm_10
TESTER :vishaaaal
Editorialist : lamda_cdm_10
DIFFICULTY
Easy-Medium
PREREQUISITES
Segment-trees , Euler tour
PROBLEM
Given a tree where all nodes are unmarked and rooted at node 1. For a given query you need to find the closest marked node which lies in its subtree and after answering the query you set the node in the query to be marked.
EXPLANATION
First, we will be maintaining an " IN " array and an “OUT” array which will basically store the In time and out - time of the nodes when we do a depth-first search on the given tree. This trick is called EULER TOUR .
Now let’s consider we are currently answering the query for Node Q . Which has
IN[Q] = X
OUT[Q] =Y
so for all the descendant nodes of this node will have IN times within the range [X, Y].
so let’s maintain an array where the indexes of the array will indicate IN times and will store the level of the node and node number as a pair of integer. Now we can find the minimum within the range [X, Y] and find the node which is closest using a segment-tree or a Fenwick tree by applying “find_min” function within the range, and we will update the Q_{th} position of the array with the level of Node Q and Node number after answering the query.
TIME-COMPLEXITY
O(N+Qlog(N))
For each query we are applying a find_min function within a particular range , and before that we had to do DFS on the tree .
TIME-COMPLEXITY
SETTER'S SOLUTION
cqxAOz - Online C++0x Compiler & Debugging Tool - Ideone.com
TESTER'S SOLUTION
rVSAtc - Online C++0x Compiler & Debugging Tool - Ideone.com
Any other solution or feedback can be posted in the comments. We are always open for them .
