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 :)
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 :)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
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)