1class Trie {
2    // Trie nodes for binary representation of numbers
3    Trie[] children = new Trie[2];
4
5    // Method to insert a number into the trie
6    void insert(long number) {
7        Trie node = this;
8        // Start from the most significant bit and iterate to the least significant bit
9        for (int i = 47; i >= 0; --i) {
10            // Extract the current bit of the number
11            int bit = (int) (number >> i) & 1;
12            // Create a new Trie node if the path doesn't exist
13            if (node.children[bit] == null) {
14                node.children[bit] = new Trie();
15            }
16            // Move to the corresponding child node
17            node = node.children[bit];
18        }
19    }
20
21    // Method to find the maximum XOR of a number with all numbers already in the trie
22    long search(long number) {
23        Trie node = this;
24        long result = 0;
25        // Start from the most significant bit and iterate to the least significant bit
26        for (int i = 47; i >= 0; --i) {
27            // Extract the current bit of the number
28            int bit = (int) (number >> i) & 1;
29            if (node == null) {
30                return result;
31            }
32            // Attempt to find the opposite bit for maximum XOR
33            if (node.children[bit ^ 1] != null) {
34                result = result << 1 | 1;
35                node = node.children[bit ^ 1];
36            } else {
37                result <<= 1;
38                node = node.children[bit];
39            }
40        }
41        return result;
42    }
43}
44
45class Solution {
46    // Graph representation using adjacency list
47    private List<Integer>[] graph;
48    // Array to store values associated with each node
49    private int[] values;
50    // Array to store the running XOR sum from the root to each node
51    private long[] xorSum;
52    // Trie to store all the XOR paths
53    private Trie trie;
54    // Variable to store the maximum XOR value found
55    private long maxXor;
56
57    // Main function to calculate the maximum XOR in the tree
58    public long maxXor(int n, int[][] edges, int[] values) {
59        graph = new List[n];
60        xorSum = new long[n];
61        this.values = values;
62        // Initialize adjacency list for each node
63        Arrays.setAll(graph, k -> new ArrayList<>());
64        // Build the graph from the edge list
65        for (var edge : edges) {
66            int from = edge[0], to = edge[1];
67            graph[from].add(to);
68            graph[to].add(from);
69        }
70        // Compute XOR sum for each node from root
71        dfs1(0, -1);
72        trie = new Trie();
73        // Find maximum XOR and insert xorSum into trie
74        dfs2(0, -1);
75        return maxXor;
76    }
77
78    // Recursive DFS to record the XOR sum from the root to each node
79    private long dfs1(int node, int parent) {
80        long sum = values[node];
81        for (int adjacent : graph[node]) {
82            if (adjacent != parent) {
83                sum += dfs1(adjacent, node);
84            }
85        }
86        xorSum[node] = sum;
87        return sum;
88    }
89
90    // Recursive DFS to find the maximum XOR and insert the XOR sums into the trie
91    private void dfs2(int node, int parent) {
92        maxXor = Math.max(maxXor, trie.search(xorSum[node]));
93        for (int adjacent : graph[node]) {
94            if (adjacent != parent) {
95                dfs2(adjacent, node);
96            }
97        }
98        trie.insert(xorSum[node]);
99    }
100}
101

1#include <vector>
2#include <functional>
3
4using ll = long long; // Alias for long long data type for convenience.
5using namespace std;
6
7// A class that represents a Trie data structure for storing binary representations of numbers.
8class Trie {
9public:
10    vector<Trie*> children; // Each node has 2 children: one for bit 0, and another for bit 1.
11
12    // Constructor that initializes the children to null.
13    Trie() : children(2) {}
14
15    // Inserts a 48-bit number into the trie.
16    void insert(ll number) {
17        Trie* node = this;
18        for (int i = 47; i >= 0; --i) {
19            int bit = (number >> i) & 1; // Extract the bit at position i.
20            if (!node->children[bit])
21                node->children[bit] = new Trie(); // Create a new node if necessary.
22            node = node->children[bit]; // Move to the next node.
23        }
24    }
25
26    // Searches for the complement of x in the trie to maximize XOR.
27    ll search(ll number) {
28        Trie* node = this;
29        ll result = 0;
30        for (int i = 47; i >= 0; --i) {
31            if (!node) return result;
32            int bit = (number >> i) & 1;
33            // If the complementary bit exists, use it to maximize XOR.
34            if (node->children[bit ^ 1]) {
35                result = (result << 1) | 1;
36                node = node->children[bit ^ 1];
37            } else { // Otherwise, continue with the same bit.
38                result <<= 1;
39                node = node->children[bit];
40            }
41        }
42        return result;
43    }
44};
45
46class Solution {
47public:
48    // Returns the maximum XOR obtained by the sum of values from the root to any node.
49    long long maxXor(int n, vector<vector<int>>& edges, vector<int>& values) {
50        vector<vector<int>> graph(n); // Representation of the graph.
51        // Constructing the undirected graph from edges.
52        for (auto& edge : edges) {
53            int from = edge[0], to = edge[1];
54            graph[from].emplace_back(to);
55            graph[to].emplace_back(from);
56        }
57
58        vector<ll> prefixSum(n); // Stores the prefix sum of values from root to the node.
59      
60        // Helper function to calculate prefix sum using DFS.
61        function<ll(int, int)> dfsPrefixSum = [&](int node, int parent) -> ll {
62            ll total = values[node];
63            for (int neighbor : graph[node]) {
64                if (neighbor != parent) {
65                    total += dfsPrefixSum(neighbor, node);
66                }
67            }
68            prefixSum[node] = total;
69            return total;
70        };
71      
72        // Initial call to calculate prefix sums.
73        dfsPrefixSum(0, -1);
74
75        Trie trie; // Trie to store the prefix sums.
76        ll result = 0;
77
78        // Helper function to find the maximum XOR and update the trie using DFS.
79        function<void(int, int)> dfsMaxXor = [&](int node, int parent) {
80            result = std::max(result, trie.search(prefixSum[node])); // Update the result.
81            for (int neighbor : graph[node]) {
82                if (neighbor != parent) {
83                    dfsMaxXor(neighbor, node); // Explore neighbors.
84                }
85            }
86            trie.insert(prefixSum[node]); // Insert prefix sum into trie.
87        };
88
89        // Initial call to find maximum XOR.
90        dfsMaxXor(0, -1);
91      
92        return result;
93    }
94};
95

1// Trie node structure for binary numbers
2class TrieNode {
3    children: TrieNode[];
4
5    constructor() {
6        this.children = []; // Initialize children to be empty
7    }
8}
9
10// Inserts a 48-bit number into the trie
11function insert(number: bigint, root:TrieNode): void {
12    let node = root;
13    for (let i = 47; i >= 0; --i) {
14        const bit = (number >> BigInt(i)) & BigInt(1); // Extract the bit at position i
15        if (!node.children[Number(bit)]) {
16            node.children[Number(bit)] = new TrieNode(); // Create a new node if necessary
17        }
18        node = node.children[Number(bit)]; // Move to the next node
19    }
20}
21
22// Searches for the complement of x in the trie to maximize XOR
23function search(number: bigint, root: TrieNode): bigint {
24    let node = root;
25    let result = BigInt(0);
26    for (let i = 47; i >= 0; --i) {
27        if (!node) return result;
28        const bit = (number >> BigInt(i)) & BigInt(1);
29        if (node.children[Number(bit ^ BigInt(1))]) {
30            result = (result << BigInt(1)) | BigInt(1);
31            node = node.children[Number(bit ^ BigInt(1))];
32        } else {
33            result <<= BigInt(1);
34            node = node.children[Number(bit)];
35        }
36    }
37    return result;
38}
39
40// Calculates the prefix sum of values from the root to the node using DFS
41function calculatePrefixSum(node: number, parent: number, graph: number[][], values: number[], prefixSum: bigint[]): bigint {
42    let total = BigInt(values[node]);
43    for (const neighbor of graph[node]) {
44        if (neighbor !== parent) {
45            total += calculatePrefixSum(neighbor, node, graph, values, prefixSum);
46        }
47    }
48    prefixSum[node] = total;
49    return total;
50}
51
52// Finds the maximum XOR value by exploring all paths and updates the trie
53function dfsMaxXor(node: number, parent: number, graph: number[][], values: number[], prefixSum: bigint[], result: bigint, root: TrieNode): bigint {
54    result = max(result, search(prefixSum[node], root));  // Update the result with the maximum XOR found
55    for (const neighbor of graph[node]) {
56        if (neighbor !== parent) {
57            dfsMaxXor(neighbor, node, graph, values, prefixSum, result, root); // Explore neighbors
58        }
59    }
60    insert(prefixSum[node], root); // Insert the current prefix sum into the trie
61    return result;
62}
63
64function maxXor(n: number, edges: number[][], values: number[]): bigint {
65    const graph: number[][] = Array.from({length: n}, () => []); // Representation of the graph
66    // Constructing the undirected graph from edges
67    for (const [from, to] of edges) {
68        graph[from].push(to);
69        graph[to].push(from);
70    }
71
72    const prefixSum: bigint[] = new Array(n); // Stores the prefix sum of values from root to the node
73
74    // Initial call to calculate prefix sums
75    calculatePrefixSum(0, -1, graph, values, prefixSum);
76
77    const root = new TrieNode(); // Trie to store the binary representations of the prefix sums
78    let result = BigInt(0);
79
80    // Initial call to find the maximum XOR
81    result = dfsMaxXor(0, -1, graph, values, prefixSum, result, root);
82
83    return result;
84}
85
86// Utility function to find the maximum of two BigIntegers
87function max(a: bigint, b: bigint): bigint {
88    return a > b ? a : b;
89}
90