How can i solve "RECURSION LOVE", a recent codefusion question in an efficient way?

Link: https://www.codechef.com/COFN2019/problems/CFD020

Read about binary lifting.

I have seen the algorithm and it is used to calculate Lowest common ancestor in a binary tree in an efficient way. How does the algorithm related to this question?

1 Like

You should read it once more. Yes it is used to calculate LCA, but there’s no such restriction of a binary tree. It works on any tree.

“Binary” in binary lifting has to do with binary decomposition of the path length and not the structure of tree.

The whole point is that you want to traverse a fixed distance but only through parent pointers, which can be either done in a naive way by just moving an unit distance each time or in an efficient way by using binary lifting.

Since you have already studied it once, it might be easier for you to go through my code. If you still have any issue understanding it or the concept, just reply here.

Solution

@mr_dot_convict Sir, can you please check my code ,why its giving WA. It’s exactly same as your code.Thank You!

https://www.codechef.com/viewsolution/28514334

Solved it !! Thanks Anyways.

1 Like