Core Idea - Query Method

The $getKthAncestor(node, k)$ method should return the $k$-th ancestor, or $-1$ if it does not exist. Use the same binary decomposition loop. If at any point node becomes $-1$ (past the root), return $-1$. Otherwise, after the loop, return the final node. Time: $O(\log k)$ per query.

In the worst case, $k = n$, so queries take $O(\log n)$. The method body is just a few lines: a loop over bits of $k$ with jumps through the $up$ table.