Блог пользователя Peace_789

Planets Queries I — CSES (Doubt)
Автор Peace_789, история, 4 года назад, По-английски

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 :)

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить