1938. 最大基因差查询

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]

约束条件：

2 <= parents.length <= 10^5
对于不是根的每个节点 i，0 <= parents[i] <= parents.length - 1
parents[root] == -1
1 <= queries.length <= 3 * 10^4
0 <= nodei <= parents.length - 1
0 <= vali <= 2 * 10^5

解题思路

这是一道结合了树遍历、字典树（Trie）和位操作的高难度题目。

核心思路：

离线处理查询：将每个查询按照节点分组，这样在DFS遍历到某个节点时，就可以处理所有以该节点为起点的查询。
字典树优化XOR查询：对于任意数值val，要找到与其XOR结果最大的数，可以使用字典树。从高位到低位，尽量选择与val当前位相反的路径。
DFS + 动态维护路径：使用DFS遍历树，在访问节点时将其加入字典树，回溯时将其从字典树中删除。这样保证字典树中始终只包含当前节点到根路径上的所有节点值。

具体算法：

构建邻接表表示树的结构
将查询按节点分组
实现支持插入/删除的字典树，用于快速找到最大XOR值
DFS遍历树，在每个节点处理对应的查询
利用字典树中当前路径上的所有节点值，找到与查询值XOR的最大结果

这种方法的时间复杂度为O(n * 18 + q * 18)，其中18是因为节点值最大为10^5，需要18个二进制位。空间复杂度为O(n * 18)用于存储字典树。

代码实现

class Solution {
public:
    struct TrieNode {
        TrieNode* children[2];
        int count;
        TrieNode() {
            children[0] = children[1] = nullptr;
            count = 0;
        }
    };
    
    TrieNode* root;
    vector<int> result;
    vector<vector<pair<int, int>>> nodeQueries;
    vector<vector<int>> children;
    
    void insert(int val) {
        TrieNode* node = root;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (!node->children[bit]) {
                node->children[bit] = new TrieNode();
            }
            node = node->children[bit];
            node->count++;
        }
    }
    
    void remove(int val) {
        TrieNode* node = root;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            node = node->children[bit];
            node->count--;
        }
    }
    
    int findMaxXor(int val) {
        TrieNode* node = root;
        int result = 0;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node->children[oppositeBit] && node->children[oppositeBit]->count > 0) {
                result |= (1 << i);
                node = node->children[oppositeBit];
            } else {
                node = node->children[bit];
            }
        }
        return result;
    }
    
    void dfs(int node) {
        insert(node);
        
        for (auto& query : nodeQueries[node]) {
            result[query.second] = findMaxXor(query.first);
        }
        
        for (int child : children[node]) {
            dfs(child);
        }
        
        remove(node);
    }
    
    vector<int> maxGeneticDifference(vector<int>& parents, vector<vector<int>>& queries) {
        int n = parents.size();
        children.resize(n);
        nodeQueries.resize(n);
        result.resize(queries.size());
        root = new TrieNode();
        
        int rootNode = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) {
                rootNode = i;
            } else {
                children[parents[i]].push_back(i);
            }
        }
        
        for (int i = 0; i < queries.size(); i++) {
            nodeQueries[queries[i][0]].push_back({queries[i][1], i});
        }
        
        dfs(rootNode);
        return result;
    }
};

class Solution:
    def maxGeneticDifference(self, parents: List[int], queries: List[List[int]]) -> List[int]:
        class TrieNode:
            def __init__(self):
                self.children = [None, None]
                self.count = 0
        
        def insert(val):
            node = root
            for i in range(17, -1, -1):
                bit = (val >> i) & 1
                if not node.children[bit]:
                    node.children[bit] = TrieNode()
                node = node.children[bit]
                node.count += 1
        
        def remove(val):
            node = root
            for i in range(17, -1, -1):
                bit = (val >> i) & 1
                node = node.children[bit]
                node.count -= 1
        
        def find_max_xor(val):
            node = root
            result = 0
            for i in range(17, -1, -1):
                bit = (val >> i) & 1
                opposite_bit = 1 - bit
                if node.children[opposite_bit] and node.children[opposite_bit].count > 0:
                    result |= (1 << i)
                    node = node.children[opposite_bit]
                else:
                    node = node.children[bit]
            return result
        
        def dfs(node):
            insert(node)
            
            for val, query_idx in node_queries[node]:
                result[query_idx] = find_max_xor(val)
            
            for child in children[node]:
                dfs(child)
            
            remove(node)
        
        n = len(parents)
        children = [[] for _ in range(n)]
        node_queries = [[] for _ in range(n)]
        result = [0] * len(queries)
        root = TrieNode()
        
        root_node = -1
        for i in range(n):
            if parents[i] == -1:
                root_node = i
            else:
                children[parents[i]].append(i)
        
        for i, (node, val) in enumerate(queries):
            node_queries[node].append((val, i))
        
        dfs(root_node)
        return result

public class Solution {
    public class TrieNode {
        public TrieNode[] Children;
        public int Count;
        
        public TrieNode() {
            Children = new TrieNode[2];
            Count = 0;
        }
    }
    
    private TrieNode root;
    private int[] result;
    private List<(int, int)>[] nodeQueries;
    private List<int>[] children;
    
    private void Insert(int val) {
        TrieNode node = root;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            if (node.Children[bit] == null) {
                node.Children[bit] = new TrieNode();
            }
            node = node.Children[bit];
            node.Count++;
        }
    }
    
    private void Remove(int val) {
        TrieNode node = root;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            node = node.Children[bit];
            node.Count--;
        }
    }
    
    private int FindMaxXor(int val) {
        TrieNode node = root;
        int result = 0;
        for (int i = 17; i >= 0; i--) {
            int bit = (val >> i) & 1;
            int oppositeBit = 1 - bit;
            if (node.Children[oppositeBit] != null && node.Children[oppositeBit].Count > 0) {
                result |= (1 << i);
                node = node.Children[oppositeBit];
            } else {
                node = node.Children[bit];
            }
        }
        return result;
    }
    
    private void DFS(int node) {
        Insert(node);
        
        foreach (var query in nodeQueries[node]) {
            result[query.Item2] = FindMaxXor(query.Item1);
        }
        
        foreach (int child in children[node]) {
            DFS(child);
        }
        
        Remove(node);
    }
    
    public int[] MaxGeneticDifference(int[] parents, int[][] queries) {
        int n = parents.Length;
        children = new List<int>[n];
        nodeQueries = new List<(int, int)>[n];
        result = new int[queries.Length];
        root = new TrieNode();
        
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
            nodeQueries[i] = new List<(int, int)>();
        }
        
        int rootNode = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) {
                rootNode = i;
            } else {
                children[parents[i]].Add(i);
            }
        }
        
        for (int i = 0; i < queries.Length; i++) {
            nodeQueries[queries[i][0]].Add((queries[i][1], i));
        }
        
        DFS(rootNode);
        return result;
    }
}

var maxGeneticDifference = function(parents, queries) {
    class TrieNode {
        constructor() {
            this.children = [null, null];
            this.count = 0;
        }
    }
    
    const root = new TrieNode();
    const n = parents.length;
    const children = Array.from({length: n}, () => []);
    const nodeQueries = Array.from({length: n}, () => []);
    const result = new Array(queries.length);
    
    function insert(val) {
        let node = root;
        for (let i = 17; i >= 0; i--) {
            const bit = (val >> i) & 1;
            if (!node.children[bit]) {
                node.children[bit] = new TrieNode();
            }
            node = node.children[bit];
            node.count++;
        }
    }
    
    function remove(val) {
        let node = root;
        for (let i = 17; i >= 0; i--) {
            const bit = (val >> i) & 1;
            node = node.children[bit];
            node.count--;
        }
    }
    
    function findMaxXor(val) {
        let node = root;
        let result = 0;
        for (let i = 17; i >= 0; i--) {
            const bit = (val >> i) & 1;
            const oppositeBit = 1 - bit;
            if (node.children[oppositeBit] && node.children[oppositeBit].count > 0) {
                result |= (1 << i);
                node = node.children[oppositeBit];
            } else {
                node = node.children[bit];
            }
        }
        return result;
    }
    
    function dfs(node) {
        insert(node);
        
        for (const [val, queryIdx] of nodeQueries[node]) {
            result[queryIdx] = findMaxXor(val);
        }
        
        for (const child of children[node]) {
            dfs(child);
        }
        
        remove(node);
    }
    
    let rootNode = -1;
    for (let i = 0; i < n; i++) {
        if (parents[i]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	时间复杂度	空间复杂度
总体	O(n × 18 + q × 18)	O(n × 18)
说明	n为节点数，q为查

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目