Naive Approach

The obvious solution: store each node's parent, then jump up $k$ times. For each query, start at $v$ and follow the parent pointer $k$ times. This takes $O(k)$ time per query. If $k = n-1$ (node is near a leaf, ancestor is the root), that is $O(n)$ per query. With a million queries, that is a billion operations. Too slow.

You need a faster way to jump. The bottleneck: each jump moves you only one level up. What if you could skip multiple levels at once?