##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Decompose k into powers)
To find the -th ancestor of , decompose into powers of . For each bit set in , make the corresponding jump.
For example, if (bits , , are set), jump , then , then . That is three jumps total. After all jumps, you land at the -th ancestor. Time: per query. If goes past the root during any jump, the ancestor does not exist. Return in that case.
