1938. Maximum Genetic Difference Query¶
题目信息¶
- 题号:
1938
- 难度:
Hard
- 主题:
树、位字典树、离线查询
- 原题:
- 重点:
查询节点与其任意祖先编号异或的最大值
题目重述¶
parents 描述一棵根树,节点的遗传值等于节点编号。每个查询给出节点和整数 val,返回 val 与该节点自身或任意祖先编号异或后的最大值。
自建示例¶
输入:parents = [-1,0,1], queries = [[2,3],[1,4]]
输出:[3,5]
解释:节点 2 的祖先编号为 2、1、0,最大异或为 3;节点 1 的最大异或为 1 XOR 4 = 5。
输入:parents = [-1], queries = [[0,7]]
输出:[7]
解释:唯一可选节点编号为 0。