Answering Queries

To find the $k$-th ancestor of $v$, decompose $k$ into powers of $2$. For each bit set in $k$, make the corresponding jump.

For example, if $k = 13 = 1101_2$ (bits $0$, $2$, $3$ are set), jump $2^0$, then $2^2$, then $2^3$. That is three jumps total. After all jumps, you land at the $k$-th ancestor. Time: $O(\log k)$ per query. If $v$ goes past the root during any jump, the ancestor does not exist. Return $-1$ in that case.