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 :)
# | User | Rating |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 162 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 154 |
8 | pajenegod | 147 |
9 | BledDest | 145 |
9 | Um_nik | 145 |
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 :)
Name |
---|
easiest way is binary lifting to kth parent using sparse table (similar to lca).
space complexity:O(nlogn)
Complexity:O(nlogn)
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
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))
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)