StrawberryInsha2k's blog

By StrawberryInsha2k, history, 8 months 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

»
8 months ago, # |
  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.

»
8 months ago, # |
  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.