### GrandmomPanties's blog

By GrandmomPanties, history, 22 months ago, , 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 :)  Comments (5)
 » easiest way is binary lifting to kth parent using sparse table (similar to lca).space complexity:O(nlogn)Complexity:O(nlogn)
•  » » 9 months ago, # ^ | ← Rev. 2 →   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
•  » » » 9 months ago, # ^ | ← Rev. 4 →   let's say that k has the following binary representation: 0011010This means that you need to climb up (21 = 2 nodes) + (23 = 8 nodes) + (24 = 16 nodes), the order doesn't matterTo do this you can loop over the bits of k and if the ith bit set, go up 2i nodesSince 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))
 » 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.
•  » » 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)