##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Class-based binary lifting)
Constructor:
1. Store n and parent array.
2. Compute LOG=⌈log2n⌉.
3. Build up[n][LOG]:
up[i][0] = parent[i]
up[i][j] = up[up[i][j-1]][j-1]
getKthAncestor(node,k):
1. For j=0 to LOG−1, if k&(1≪j), set node = up[node][j].
2. If node becomes −1, return −1.
3. Return node.
This runs in O(nlogn) time and uses O(nlogn) space.
