A genealogy site stores a family forest: parent[v] is the parent of person v, or -1 if v's parents are unknown. born[v] is the year v was born, and every parent is born strictly earlier than their child, so birth years strictly decrease as you walk up.
A visitor asks: "Starting from person v and following parents upward, who is the highest-up person on that line who was born in year since or later?" If v was born before since, the answer is -1.
Implement earliest_since(parent, born, queries) -> list[int] where each query is a pair (v, since); return one answer per query.
# 0 (1900) -> 1 (1930) -> 2 (1958) -> 3 (1990)
# -> 4 (1961)
parent = [-1, 0, 1, 2, 1]
born = [1900, 1930, 1958, 1990, 1961]
earliest_since(parent, born, [(3, 1950), (3, 1995), (4, 1930), (2, 1800)])
# [2, -1, 1, 0]
Constraints: 1 <= n <= 10^5, up to 10^5 queries. Family lines can be 10^5 generations deep, so walking up one parent at a time per query is too slow. Parents do not necessarily have smaller numbers than their children.
Show hint
build the jump table up[j][v] (the ancestor 2^j steps above v). For a query, try j from high to low and jump whenever the target exists and was born in since or later; since birth years are monotone along the path, the greedy jumps land on the answer.