MIKE AND OR TREE Have a look into my code and suggest changes but not give solution i am trying it

#1


first i think this qns cant be solved using square root decomposition then why given in module of it,
but i try it with graphs ,PATA NHI WHY GIVES RUNTIME ERROR

#2

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))

Refer this for better understanding -:

#3

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.