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.
⭐ Bonus: walking both employees up one boss at a time (O(n) per query) still passes; a speed test on a deep chain earns a star with O(n log n) preprocessing and O(log n) per query. That hierarchy is 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.