Best XOR Up the Chain of Command

Hard

A company has n employees numbered 0 to n - 1. Everyone except the director has exactly one manager: parent[i] is the manager of employee i, and for the director parent[i] = -1. Together this forms a tree rooted at the director. You are given queries, where queries[i] = [node, val]. For a query, look at the chain from employee node up to the director, both ends included. Pick the employee p in that chain for which val XOR p is as large as possible. Return an array whose i-th element is that maximum for the i-th query.

Example 1

parent=[-1, 0, 0, 1], queries=[[3, 6], [2, 1]] → [7, 3]

The chain from 3 to the root is 3, 1, 0, and the best is 6 XOR 1 = 7. The chain from 2 is 2, 0, with the best being 1 XOR 2 = 3.

Example 2

parent=[2, -1, 1], queries=[[0, 4]] → [6]

The root here is 1. The chain from 0 is 0, 2, 1, giving 4 XOR 0 = 4, 4 XOR 2 = 6 and 4 XOR 1 = 5, so the maximum is 6.

Constraints

2 ≤ n = len(parent) ≤ 10⁵
Exactly one employee has parent[i] = -1; for the rest 0 ≤ parent[i] < n
The manager links form a tree (no cycles)
1 ≤ len(queries) ≤ 10⁵
0 ≤ node < n
0 ≤ val ≤ 2 · 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Bit Manipulation Depth-First Search Trie Array Hash Table

Similar problems

Words That Fit Each Puzzle Hard Largest XOR of a Close Pair Hard Most Different Pair Medium XOR of a Close Pair Easy Every Way to Space the Words Hard

Input

parent=[-1, 0, 0, 1], queries=[[3, 6], [2, 1]]

Expected

[7, 3]

Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.