查询最大基因差

/*
思路：
1. 与上面的思路相同，首先构建树的结构。
2. 对于每个查询，找到对应节点到根节点路径上的所有节点。
3. 使用这些节点和查询值进行异或运算，找到最大值。
4. 返回所有查询的结果。
5. 使用 Java Stream API 进行路径节点和异或计算。
*/

import java.util.*;
import java.util.stream.*;

public class MaxGeneDifferenceStream {
    public static int[] maxGeneDifference(int[] parents, int[][] queries) {
        int n = parents.length;
        List<Integer>[] tree = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            tree[i] = new ArrayList<>();
        }
        int root = -1;
        for (int i = 0; i < n; i++) {
            if (parents[i] == -1) {
                root = i;
            } else {
                tree[parents[i]].add(i);
            }
        }

        Map<Integer, Set<Integer>> nodeToRootPath = new HashMap<>();
        buildPaths(root, new HashSet<>(), tree, nodeToRootPath);

        return Arrays.stream(queries)
                .mapToInt(query -> getMaxXor(nodeToRootPath.get(query[0]), query[1]))
                .toArray();
    }

    private static void buildPaths(int node, Set<Integer> path, List<Integer>[] tree, Map<Integer, Set<Integer>> nodeToRootPath) {
        path.add(node);
        nodeToRootPath.put(node, new HashSet<>(path));
        for (int child : tree[node]) {
            buildPaths(child, path, tree, nodeToRootPath);
        }
        path.remove(node);
    }

    private static int getMaxXor(Set<Integer> path, int val) {
        return path.stream()
                .mapToInt(p -> val ^ p)
                .max()
                .orElse(0);
    }

    public static void main(String[] args) {
        int[] parents = {3, 7, -1, 2, 0, 7, 0, 2};
        int[][] queries = {{4, 6}, {1, 15}, {0, 5}};
        System.out.println(Arrays.toString(maxGeneDifference(parents, queries))); // 输出 [6, 14, 7]
    }
}