Comparison to Naive Approach

Naive approach: $O(1)$ preprocessing, $O(k)$ per query. For $q$ queries with $k \approx n$, that is $O(qn)$ total. Binary lifting: $O(n \log n)$ preprocessing, $O(\log k)$ per query. Total: $O(n \log n + q \log n)$. If $q$ is large, binary lifting is orders of magnitude faster. For $n = 100,000$ and $q = 1,000,000$, naive takes billions of operations.

Binary lifting takes millions. That is the difference between timing out and passing comfortably.