# REC20D- Editorial

Problem D : Glass Stepping Stones
SETTER : lamda_cdm_10
TESTER :vishaaaal
Editorialist : lamda_cdm_10

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 .

2 Likes