Блог пользователя arjitkansal

Автор arjitkansal, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Spoiler