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≤50,000, up to 50,000 queries. Binary lifting handles this easily. The constructor runs in O(nlogn) and each query takes O(logn) time.