I am thinking of this question as a question of tree but as this is in square root Decomposition so it must be having a approach using square root decomposition.
Any hint or approach , how to approach Mike and OR tree question
The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into sqrt(n) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest node with value 1 using bfs. To answer the query we should update this value by shortest distances to nodes with value 1 in current block.
The solution becomes simple. Every sqrt(n) queries we make simple bfs and for every node v WE calculate value d[v] — the shortest distance to some node with value 1 from node v. Then to answer the query of type 2 you should calculate min(d[v], dist(v, u)), where u — every node with value 1, which is updated in current block of length sqrt(n). dist(v,u) can be calculated by using sparse table for LCA,
dist(v,u) = level_v + level_u - 2*level_lca_vu
Time Complexity : O(N * sqrt(N) * log(N))
Its a very difficult problem. You can have a look at implementation here
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.