retr0coderxyz's blog

Help regarding QTree2
By retr0coderxyz, history, 4 years ago, In English

Hey guys!

I am trying to solve Qtree2 from SPOJ after learning about LCA using binary lifting.Problem

There are 2 parts to this question one is to find distance between any two given nodes and the other part is to find kth node in the path between 2 nodes.

While I was able to solve the first part, but I am stuck in solving second part, I tried a lot (only clue i was able to find out is that the path goes through LCA of two nodes) and couldn't proceed from there.

It would be really helpful if someone could give a detailed explanation using binary lifting it would be great. Thank you so much!

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone please?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +3 Vote: I do not like it

    Suppose A and B have lca C.. And let distance between A and B is x. Then the Kth node on the path from A to B is either on the part of the subtree having A or on the part of the subtree having B. I mean the Kth node will be an ancestor of either A or B for sure.

    If K is > dist(A,C) then it is an ancestor of B. Else it is an ancestor of A.

    Then you can determine which ancestor of A or B it is and make ancestor query to get the answer.

    → Reply