Building the Table

Build the table column by column. First, fill column $0$ (parents). Then fill column $1$ using column $0$. Then fill column $2$ using column $1$. And so on. For each column $j$ from $1$ to $\log n$, and for each node $v$, set:

up[v][j] = up[up[v][j-1]][j-1]

Time: $O(n \log n)$, because you fill $n \log n$ entries, each in $O(1)$ time. Space: $O(n \log n)$ for the table. For $n = 200,000$, the table has about $3.4$ million entries.