Core Idea - Constructor Preprocessing

The constructor is called once with the tree structure (parent array). This is where you build the $up$ table. Compute $\log n$ (around $16$ for $n = 50,000$). Allocate up[n][log n]. Fill it column by column as before. Time: $O(n \log n)$. This runs only once, so it is fine even if $n$ is large.

Each query then reads from the precomputed table. The amortized cost per operation is low because the preprocessing dominates.