Peace_789's blog

By Peace_789, history, 8 months ago, In English

Hello guys , I am having trouble solving this problem

You can read problem statement here also.

Statement

So , any hint to solve this problem will be grateful.

Thanks in advance :)

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

»
8 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Hey this is a classic Binary Lifting problem.

my own explanation for me

See if you can understand it and try the problem on ur own. Cheers

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey bro , Here is what I had tried.

    Detect all cycles and keep track of all cycles where each node in cycle is given node no.

    then for node x in query , if x is already part of some cycle then it's very easy to ans. the kth node.

    but for case where node isn't part of any cycle , I tried binary lifting on inverted tree (in which edge causing cycles are erased.) FOR THIS CASE , I am unable to code.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Initially, I tried the cycle approach which let to TLE for me. But if you notice it clearly its plain binary Lifting.

      Precompute jumps for each node. and then in query node walk or jump in binary value of k. You will get the answer.

      Spoiler
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I was thinking on exactly same line. Though a pure binary lifting approach works.