The k-th Ancestor Problem

Given a tree and a node $v$, who is the $k$-th ancestor of $v$?

The $k$-th ancestor is the node you reach by going up $k$ steps toward the root. For example, if $v$ has parent $p$, then $p$ is the $1$st ancestor. The parent of $p$ is the $2$nd ancestor. The root is the depth[v]-th ancestor.

The naive approach jumps one parent at a time, taking $O(k)$ per query. If $k$ is close to $n$ and you have $q$ queries, that is $O(nq)$ total.