Company Queries I - Implementation

Build $up$ table:

for i = 2 to n:
 up[i][0] = parent[i]
up[1][0] = 1 // root's parent is itself

for j = 1 to log(n):
 for i = 1 to n:
 up[i][j] = up[up[i][j-1]][j-1]

Answer query $(v, k)$:

for j = log(n) down to 0:
 if k >= 2^j:
 v = up[v][j]
 k = k - 2^j
return v

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