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

Distance Between Nodes in A Tree
Автор jhjfbsbfkbjfnfnfjfj, история, 5 лет назад, По-английски

In a weighted tree, how to find for some node (u) the distance to another node (v) (answering Q queries effeiciently)? Constraints N <=10^3, Queries <=10^3

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Since N is small you can apply BFS starting from u in each query and print the distance of node v which will take O(n) time for each query. An efficient way to answer each query in O(logn) is using LCA which can be found in O(logn) using binary lifting.

→ Ответить
»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I teach all these concepts with practice problems , here is the graph theory playlist where you can find this concept along with other concepts. https://www.youtube.com/playlist?list=PL2q4fbVm1Ik64I3VqbVGRfl_OgYzvzt9m hope this helps.

→ Ответить