Problem - Kth Ancestor of a Tree Node

You are given a tree with $n$ nodes. Implement a class that supports $getKthAncestor(node, k)$ queries. This is exactly the binary lifting problem, but in an object-oriented wrapper.

You will build the $up$ table in the constructor, then answer queries. Constraints: $n \leq 50,000$, up to $50,000$ queries. Binary lifting handles this easily. The constructor runs in $O(n \log n)$ and each query takes $O(\log n)$ time.