A company has n employees numbered 1..n. Employee 1 is the director, and everyone else has one direct boss, so the hierarchy is a tree rooted at 1. bosses[i] is the direct boss of employee i + 2 (the list has length n - 1).
For each query (a, b), find the lowest common boss: the employee furthest from the director who is a boss (directly or indirectly) of both a and b. An employee counts as their own boss here, so if a is above b in the hierarchy, the answer is a.
Implement company_queries_ii(n: int, bosses: list[int], queries: list[tuple[int, int]]) -> list[int], returning one answer per query.
# 1
# / \
# 2 3
# / \ \
# 4 5 6
company_queries_ii(6, [1, 1, 2, 2, 3], [(4, 5), (4, 6), (2, 5), (6, 6)])
# [2, 1, 2, 6]
Constraints: 1 <= n <= 2 * 10^5, up to 2 * 10^5 queries. Don't assume a boss has a smaller number than their employee.
Walking both employees up one boss at a time is O(n) per query on a long chain. Aim for O(n log n) preprocessing and O(log n) per query. The hierarchy can be 2 * 10^5 levels deep, so avoid recursion.
Show hint
First bring the deeper employee up to the other's depth. After that, the two climb in lockstep, and you want the highest point where they are still different; if you can jump 2^j bosses at once, you can find it one bit at a time.