GrandmomPanties's blog

K'th ancestor of all nodes
By GrandmomPanties, history, 8 years ago, In English

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

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

»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

space complexity:O(nlogn)

Complexity:O(nlogn)

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
8 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply