Binary Lifting for Successors

To find $f^k(x)$ for large $k$, you cannot simulate $k$ steps. That takes $O(k)$ time. If $k = 10^9$, you time out.

Instead, precompute $f^{2^i}(x)$ for all $i$ and all $x$. You can reach any $k$-th successor by combining powers of $2$. This is binary decomposition. This is binary lifting. It reduces $O(k)$ to $O(\log k)$ per query after $O(n \log n)$ preprocessing. The preprocessing pays off when you have multiple queries.

Space complexity is $O(n \log n)$ for the data structures used.