Can you find the kth ancestor in a splay tree? A link-cut tree is just a splay tree.

when you're asked for kth ancestor of node V:

1. Store in each node the size of its subtree (in the splay tree not the original tree)

2. Access V

3. Now there should be >= K nodes to the left of node V, go to the left child of V and use sub tree sizes to find kth node from the right

How to do it:

Let's say you have L nodes to left and R nodes to the right

if R == K-1: current node is the kth ancestor

if R > K-1: kth ancestor is in right subtree

if R < K-1: kth ancestor is in left subtree, when you go left, you're objective changes to finding the (K — R — 1)th node (as K nodes from the right and root node were discarded)

In case the root was fixed, you can just do dfs from the root and use a stack to keep track of all ancestors, when you get to Node V, the answer is in stack[size — K]