The tutorial discusses the application on arrays, which is pretty clear. But how do I apply the concept on tree?
Please provide a clear hint (no code).
How do I apply the concept on trees?
@shivama_700
For a graph you are given some queries and following two operations
update operation : make a node value to 1
query operation : output the minimum distance of a node with from a node with value 1
Initially the node 1 has value 1 and all other node has value 0
Now , you can use a dfs based approach with a little mix of dp
you can have a dist array which will store the minimum distance of a node with some node with value 1 So, what you can do is whenever you make a node(say X) value to 1 start dfs considering it as root and traverse down the root increasing the level value by 1 whenever you go one level down, and take minimum of the dist[ child node] and level (relative of our X node)
and in query operation just output dist[node]
I don’t think it will work, there are 10**5 queries, at each update , I will have to update the whole dp table. So the overall time complexity will be (n*m) which will give TLE.
Also since this question is present in square root decomposition section, i think it’s gotta do with it.
@shivama_700 ok use this way then using 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))
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.
How will I flatten the tree?