Algorithm

Constructor:

$1.$ Store $n$ and parent array.

$2.$ Compute $LOG = \lceil \log_2 n \rceil$.

$3.$ Build up[n][LOG]:

up[i][0] = parent[i]

up[i][j] = up[up[i][j-1]][j-1]

$getKthAncestor(node, k)$:

$1.$ For $j = 0$ to $LOG-1$, if $k \& ($1$\ll j)$, set node = up[node][j].

$2.$ If node becomes $-1$, return $-1$.

$3.$ Return node.

This runs in $O(n \log n)$ time and uses $O(n \log n)$ space.