This question has confused me for a long time, because I was asked during the interview: Could you search LCA in constant time? You can preprocess the tree... I google it and maybe we can solve it using the concept of huffman (like mark each node using 0 or 1 and do some bit manipulation to get the common prefix, I don't know :\ ). But I am still not able to figure out the correct solution. Could anyone help me? Thank you.
Any ideas for O(1) time with preprocess (?)


There is a wellknown algorithm for that. Please check out Tarjan's offline LCA algorithm