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.
There is a well-known algorithm for that. Please check out Tarjan's off-line LCA algorithm
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.