arjitkansal's blog

By arjitkansal, history, 6 years ago, In English

It has been months, I've not able to think of any solution to solve this problem "Component Tree".

link to the problem

As this is Gym Problem, I'm not able to look for the solutions. It would be a great help if someone can provide me with the hints to solve the problem.

Thanks :)

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

I think we can solve it using idea of HLD. Maintain map or vector of pair(key, position in chain) for each heavy path. Then we can binary search to get the lowest vertex which contains given key in O(logn). Hence total complexity for each query is O(log2n). Not sure if this was the intended soln.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

think about the time to enter the node and exit. No complicated knowledge required.

Spoiler