Peace_789's blog

By Peace_789, history, 4 years 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

| Write comment?
»
4 years 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

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.