Every binary-lifting trick (k-th ancestor, LCA) starts with the same table: up[j][v] is the node you reach by going 2^j steps up from v. Row 0 is just the parent. Every later row doubles the previous one: going up 2^j steps is going up 2^(j-1) steps, twice.
You get a rooted forest as parent, a list of length n where parent[v] is the parent of node v, or -1 if v is a root. Implement build_jump_table(parent) -> list[list[int]]:
- Return exactly
LOG = n.bit_length()rows, each of lengthn(that's enough rows for any jump up tonsteps). up[0][v] = parent[v].up[j][v] = up[j-1][ up[j-1][v] ], and-1whenever the walk runs off the top of the tree.
# chain 0 <- 1 <- 2 <- 3 <- 4 (0 is the root)
build_jump_table([-1, 0, 1, 2, 3])
# [[-1, 0, 1, 2, 3], 1 step up
# [-1, -1, 0, 1, 2], 2 steps up
# [-1, -1, -1, -1, 0]] 4 steps up
Constraints: 1 <= n <= 10^5. Don't assume a parent has a smaller number than its child. There may be several roots.
Show hint
build the rows in order j = 1, 2, ...; each row only reads the row before it, so the order of the nodes doesn't matter.