claporslap's blog

By claporslap, 7 years ago, In English

How can I calculate this with efficiency without using HLD or Link Cut Trees? I tried doing it with Binary Lifting but I am not able to do it correctly. Please guide me. Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

You are in the right path if you tried doing it using binary lifting. Have you managed to succeed in doing a regular binary lifting (just to find the LCA of 2 vertices)? If not I recommend you reading this blog

Now, if you understand how to find LCA of 2 vertices, you do almost the same thing you did for calculating the parenting array but instead you do it for the length of edges

pre-process example

For a query it is again very similar to finding the LCA of 2 vertices.