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

K'th ancestor of all nodes
Автор GrandmomPanties, история, 8 лет назад, По-английски

We have a tree with n(n < 1e5) nodes and we have a constant k(k < 1e5) can we store the k'th ancestor of all nodes in an array or there is no way to do that??? Thank you for helping :)

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

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

easiest way is binary lifting to kth parent using sparse table (similar to lca).

space complexity:O(nlogn)

Complexity:O(nlogn)

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Hi teja349 how can I do the binary search in O(logn)? I already know it in O(logn*logn) because I know the kth parent in O(logn) plus the binary search

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
      ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      let's say that k has the following binary representation: 0011010

      This means that you need to climb up (21 = 2 nodes) + (23 = 8 nodes) + (24 = 16 nodes), the order doesn't matter

      To do this you can loop over the bits of k and if the ith bit set, go up 2i nodes

      Since we have O(log2(n)) bits, we go up by a power of two and we do O(1) work on the sparse table, the overall complexity is O(log2(n))

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

You can solve in O(N) by maintaining an explicit dfs stack in a vector as you dfs from the root. From each node you then look at the kth last thing in the vector if it exists.

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I think this is actually much easier than using a sparse stable (although sparse tables can be easily extended to non constant k-th ancestor queries)

    → Ответить