Space Improvement Note

If $n$ is huge (say, $10^6$), the $O(n \log n)$ space might be tight. You can improve by only storing up[v][j] for $j$ up to the depth of $v$. For example, if $v$ has depth $5$, you only need up[v][0] through up[v][2] (since $2^3 = 8 > 5$). This saves space in shallow trees.

But for most problems, the standard $O(n \log n)$ space is fine. Only optimize when the memory limit is tight and the tree is known to be shallow.