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 | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
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 :)
Название |
---|
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)