How can we approach this question with square root decomposition?
I can think of bfs traversal to find the first node having 1.
how can we devide the tree into blocks?
Mike and OR tree approach not clear
Hey @abhir26
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))