jhjfbsbfkbjfnfnfjfj's blog

Distance Between Nodes in A Tree
By jhjfbsbfkbjfnfnfjfj, history, 6 years ago, In English

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

  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
6 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
6 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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.

→ Reply