#1938
Maximum Genetic Difference Query
candidate master · 1520 · lc hard +32 · premium · verified · 46.6% accepted · 415 likes · top 31%
Description
You are given a rooted tree of n nodes numbered 0 to n - 1 where node x has genetic value x. The parents array gives each node's parent (parents[x] = -1 for the root).
For each query [nodei, vali], find the maximum XOR of vali with any node's genetic value on the path from nodei to the root (inclusive).
Return array ans where ans[i] is the result for query i.
Example 1:
Input: parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
Output: [2,3,7]
Explanation: The queries are processed as follows:
- [0,2]: The node with the maximum genetic difference is 0, with a difference of 2 XOR 0 = 2.
- [3,2]: The node with the maximum genetic difference is 1, with a difference of 2 XOR 1 = 3.
- [2,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.
Example 2:
Input: parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
Output: [6,14,7]
Explanation: The queries are processed as follows:
- [4,6]: The node with the maximum genetic difference is 0, with a difference of 6 XOR 0 = 6.
- [1,15]: The node with the maximum genetic difference is 1, with a difference of 15 XOR 1 = 14.
- [0,5]: The node with the maximum genetic difference is 2, with a difference of 5 XOR 2 = 7.
Code
1
2
3