**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 .