##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
Using centroid ancestors
For each node , store = distance from to its -th centroid ancestor. Since centroid tree depth is , The operation takes space.
Query : find the lowest centroid that is an ancestor of both and in the centroid tree.
Then: To find the common centroid ancestor, walk up from both and until you meet. With preprocessing, The operation takes time.
