Hello codeforces!
I recently got interested in the LCA problem and read a lot about it. I learned three methods for computing LCA queries:
Using Sparse Table (But i didn't like that approach since the 2-d array gives me outofmemory exception when number of nodes is 10^5 )
Transforming my rooted tree into an array and apply segment trees on it. This method works well for me but takes much too long to code.
Using Union-Find data structure.
Which approach do you use and why? Thanks!
I use ST. I think it's the most convinient one.
It isn't. You have O(NlogN) memory and you only get O(logN) per query.
HPD is a much better choice.
what does HPD stands for?
Heavy Path Decomposition
But HPD isn't much easy to code. I think it's easier and faster to use ST when there are enough memory.
If the time and memory limits allow it, I would go for binary lifting method. Otherwise, I will most likely code heavy-light decomposition which gives O(N) preprocessing, O(N) memory and O(logN) per query :)
Nice! but binary lifting is slow with a query of O(log^2 n)
Actually it's O(logN), what makes it worse than HLD is the preprocessing time and memory complexity both of O(NlogN). But it's much easier to code so that's my first choice if the memory and time limit allow it, as I said :)
I use sparse table (
parent[lgN][N]) as it's easy to code and doesn't require any additional knowledge (segment trees).BTW, if N=100000, 4*17*100000 = 6.8 MB. Where is your MLE?
how is it [logN][N] ? My implementation use parent[N][N] Can you provide a code of your approach?
Thanks!
Seems that you haven't learned anything, lol. Here you are: 10077331
You can implement HLD without Segment Tree, and it works for LCA problems. Easier to code for me. Which one do you find faster in practice ??