Take a 2^(j−1)-link jump to the midpoint, then the same-size jump again. If either jump has no ancestor, the longer jump is also missing.

up[j][v] stores the ancestor 2^j links above v. Build row j from row j−1 for every node. To answer k, consume its binary digits; each set bit selects a saved jump. Guard −1 before indexing, because Python would otherwise interpret it as the last element. k≥n is necessarily above the root of an n-node tree. This is preprocessing to trade memory and initial work for many fast queries.

What the function promises: parent describes a rooted tree with root 0 and parent[0]=−1. TreeAncestor.get_kth(node,k) returns the k-th ancestor or −1. k is nonnegative; k=0 returns the node itself.

class TreeAncestor:
    def __init__(self, parent):
        self.n = len(parent)
        self.up = [list(parent)]
        for _ in range(1, max(1, self.n.bit_length())):
            previous = self.up[-1]
            self.up.append([
                -1 if previous[v] == -1 else previous[previous[v]]
                for v in range(self.n)
            ])

    def get_kth(self, node, k):
        if not 0 <= node < self.n or k < 0:
            raise ValueError("Need a valid node and nonnegative k")
        if k >= self.n:
            return -1
        bit = 0
        while k and node != -1:
            if k & 1:
                node = self.up[bit][node]
            k >>= 1
            bit += 1
        return node

tree = TreeAncestor([-1, 0, 1, 2, 3, 4, 5])
assert tree.get_kth(6, 6) == 0
assert tree.get_kth(6, 7) == -1
assert tree.get_kth(3, 0) == 3

Work and storage: O(n log(n+1)) preprocessing time and space; O(log(k+1)) query work within the n-node bound. One or two queries may not justify building the table.

When to recognize it: Save jumps of 1, 2, 4, 8… links. Combine a few saved jumps to cover k.

Check before applying it: This saves repeated queries after preprocessing. An ancestor above the root does not exist; guard the −1 sentinel.

Also store depths. Lift the deeper vertex to the same depth. If the vertices differ, inspect powers from largest to smallest and lift both only when their candidate ancestors differ. They finish immediately below the LCA; their parent is the answer. The existing LCA lesson explains the single-query alternative.