查询最大基因差

标签: 位运算 字典树 数组

难度: Hard

给你一棵 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

Submission

运行时间: 2845 ms

内存: 107.5 MB

class Trie:
    left: "Trie" = None
    right: "Trie" = None
    # 由于我们的字典树需要支持删除数的操作
    # 因此这里使用 cnt 变量进行记录该节点对应的数的个数
    cnt: int = 0

class Solution:

    # 最大的数的二进制表示不会超过 18 位
    # 那么二进制位的下标范围为 [0, 17]
    MAXD = 17

    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        n = len(parents)

        # 将 parents 存储为树的形式，方便进行深度优先遍历
        edges = defaultdict(list)
        # 找出根节点
        root = -1
        for i, parent in enumerate(parents):
            if parent == -1:
                root = i
            else:
                edges[parent].append(i)

        q = len(queries)
        # 使用离线的思想，stored[i] 存储了所有节点 i 对应的询问
        stored = defaultdict(list)
        ans = [0] * q
        for i, (node, val) in enumerate(queries):
            stored[node].append((i, val))

        r = Trie()

        # 向字典树添加一个数
        def trie_insert(x: int) -> None:
            cur = r
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    if not cur.right:
                        cur.right = Trie()
                    cur = cur.right
                else:
                    if not cur.left:
                        cur.left = Trie()
                    cur = cur.left
                cur.cnt += 1

        # 对于给定的 x，返回字典树中包含的数与 x 进行异或运算可以达到的最大值
        def trie_query(x: int) -> int:
            cur, ret = r, 0
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    if cur.left and cur.left.cnt:
                        ret |= (1 << i)
                        cur = cur.left
                    else:
                        cur = cur.right
                else:
                    if cur.right and cur.right.cnt:
                        ret |= (1 << i)
                        cur = cur.right
                    else:
                        cur = cur.left
            return ret

        # 从字典树中删除一个数
        def trie_erase(x: int) -> None:
            cur = r
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    cur = cur.right
                else:
                    cur = cur.left
                cur.cnt -= 1

        # 深度优先遍历
        def dfs(u: int) -> None:
            trie_insert(u)
            for idx, num in stored[u]:
                ans[idx] = trie_query(num)
            for v in edges[u]:
                dfs(v)
            trie_erase(u)

        dfs(root)
        return ans

Explain

题解利用字典树（Trie）结合深度优先搜索（DFS）来解决最大基因差问题。首先，根据输入的parents数组，构建一棵树并找出根节点。对每个节点，记录所有相关的查询。然后通过DFS遍历树，同时使用字典树动态地记录当前路径上的节点值。每次访问一个节点时，将其值加入字典树中，并对所有在该节点上的查询执行查询操作，即使用字典树寻找与查询值的最大异或结果。遍历完子节点后，从字典树中删除当前节点值以防止对其他路径的影响。这样可以确保每次查询都只与从当前节点到根节点的路径相关联。

时间复杂度: O((n + q) * logM)

空间复杂度: O(n + q + M*2^M)

class Trie:
    left: 'Trie' = None  # 左子树表示0
    right: 'Trie' = None  # 右子树表示1
    cnt: int = 0  # 记录当前节点的访问计数

class Solution:
    MAXD = 17  # 最大的数的二进制表示位数

    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        n = len(parents)
        edges = defaultdict(list)  # 建立树的边关系
        root = -1  # 根节点初始化
        for i, parent in enumerate(parents):
            if parent == -1:
                root = i
            else:
                edges[parent].append(i)
        q = len(queries)
        stored = defaultdict(list)  # 存储每个节点的查询
        ans = [0] * q  # 初始化答案数组
        for i, (node, val) in enumerate(queries):
            stored[node].append((i, val))
        r = Trie()  # 字典树的根节点

        def trie_insert(x: int) -> None:
            cur = r
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    if not cur.right:
                        cur.right = Trie()
                    cur = cur.right
                else:
                    if not cur.left:
                        cur.left = Trie()
                    cur = cur.left
                cur.cnt += 1  # 更新当前路径的计数

        def trie_query(x: int) -> int:
            cur, ret = r, 0
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    if cur.left and cur.left.cnt:
                        ret |= (1 << i)
                        cur = cur.left
                    else:
                        cur = cur.right
                else:
                    if cur.right and cur.right.cnt:
                        ret |= (1 << i)
                        cur = cur.right
                    else:
                        cur = cur.left
            return ret

        def trie_erase(x: int) -> None:
            cur = r
            for i in range(Solution.MAXD, -1, -1):
                if x & (1 << i):
                    cur = cur.right
                else:
                    cur = cur.left
                cur.cnt -= 1  # 删除时减少计数

        def dfs(u: int) -> None:
            trie_insert(u)  # 插入当前节点
            for idx, num in stored[u]:
                ans[idx] = trie_query(num)  # 执行查询
            for v in edges[u]:
                dfs(v)  # 遍历子节点
            trie_erase(u)  # 退出时从字典树中删除当前节点

        dfs(root)
        return ans

Explore

在字典树中，每个节点的`cnt`属性记录了该节点在当前路径中出现的次数。当一个节点值被插入或删除时，只有与该节点值相关的路径上的`cnt`会被增加或减少。因此，即使某个节点值从字典树中删除，只要其他路径上还有相同的节点值，这些节点的`cnt`不会变为零，它们仍然存在于字典树中。这样可以确保删除操作不会影响到那些不在当前DFS路径但共享相同节点值的其他分支的查询结果。

异或运算的性质是，相同的数异或结果为0，不同的数异或结果为1。在字典树中查询最大异或值时，目标是最大化最终得到的异或结果的数值。因此，如果当前位是1，我们会优先选择与之异或后能得到0的分支（即选择0分支），反之如果当前位是0，优先选择1分支，因为这样可以使得当前位的异或结果为1，从而使整个数值更大。

字典树（Trie）是一种树形结构，非常适合用于处理和查询字符串或二进制数据集合中的键。在处理基因值时，每个基因值可以被视为一个二进制数。字典树的每个节点代表一个二进制位（0或1），从根到某一节点的路径代表树中保存的一个完整的基因值。通过逐位插入基因值到字典树，并在每个节点记录经过该节点的路径数量（通过`cnt`属性），可以高效地查询和管理基因值。这种结构使得查询特定基因值或与其他基因值的最大异或结果都变得快速和直接。

在DFS遍历过程中，字典树中每个节点的`cnt`计数器记录了该节点被当前路径上有多少个实际节点值引用。这种计数允许我们在遍历过程中动态地管理和跟踪每个节点值的存在性。当遍历到一个新节点时，我们将其值加入字典树并将相应路径上的节点的`cnt`增加。当从一个节点回溯时，相应的节点值从字典树中删除，即将其`cnt`减少。这确保了字典树中始终只包含从当前节点到根节点的路径上的节点值，从而使得查询操作能够正确地反映出从任一节点到根节点的路径状态。