调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一棵 n 个节点的有根树,节点编号从 0 到 n - 1 。每个节点的编号表示这个节点的 独一无二的基因值 (也就是说节点 x 的基因值为 x)。两个基因值的 基因差 是两者的 异或和 。给你整数数组 parents ,其中 parents[i] 是节点 i 的父节点。如果节点 x 是树的  ,那么 parents[x] == -1 。

给你查询数组 queries ,其中 queries[i] = [nodei, vali] 。对于查询 i ,请你找到 vali 和 pi 的 最大基因差 ,其中 pi 是节点 nodei 到根之间的任意节点(包含 nodei 和根节点)。更正式的,你想要最大化 vali XOR pi 

请你返回数组 ans ,其中 ans[i] 是第 i 个查询的答案。

 

示例 1:

输入:parents = [-1,0,1,1], queries = [[0,2],[3,2],[2,5]]
输出:[2,3,7]
解释:查询数组处理如下:
- [0,2]:最大基因差的对应节点为 0 ,基因差为 2 XOR 0 = 2 。
- [3,2]:最大基因差的对应节点为 1 ,基因差为 2 XOR 1 = 3 。
- [2,5]:最大基因差的对应节点为 2 ,基因差为 5 XOR 2 = 7 。

示例 2:

输入:parents = [3,7,-1,2,0,7,0,2], queries = [[4,6],[1,15],[0,5]]
输出:[6,14,7]
解释:查询数组处理如下:
- [4,6]:最大基因差的对应节点为 0 ,基因差为 6 XOR 0 = 6 。
- [1,15]:最大基因差的对应节点为 1 ,基因差为 15 XOR 1 = 14 。
- [0,5]:最大基因差的对应节点为 2 ,基因差为 5 XOR 2 = 7 。

 

提示:

  • 2 <= parents.length <= 105
  • 对于每个 不是 根节点的 i ,有 0 <= parents[i] <= parents.length - 1 。
  • parents[root] == -1
  • 1 <= queries.length <= 3 * 104
  • 0 <= nodei <= parents.length - 1
  • 0 <= vali <= 2 * 105
通过次数
2.7K
提交次数
6.1K
通过率
43.6%


相关企业

提示 1
How can we use a trie to store all the XOR values in the path from a node to the root?

提示 2
How can we dynamically add the XOR values with a DFS search?


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
运行和提交代码需要登录
parents =
[-1,0,1,1]
queries =
[[0,2],[3,2],[2,5]]
Source