Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Peace_789's blog

Planets Queries I — CSES (Doubt)
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

Comments Comments (3)
| 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

→ Reply
  • »
    »
    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.

    → Reply
    • »
      »
      »
      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.

      → Reply