Skip to content

2479. Maximum XOR of Two Non-Overlapping Subtrees 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  TrieNode() : children(2) {}
};

class BitTrie {
 public:
  BitTrie(int maxBit) : maxBit(maxBit) {}

  void insert(long num) {
    shared_ptr<TrieNode> node = root;
    for (int i = maxBit; i >= 0; --i) {
      const int bit = num >> i & 1;
      if (node->children[bit] == nullptr)
        node->children[bit] = make_shared<TrieNode>();
      node = node->children[bit];
    }
  }

  long getMaxXor(long num) {
    long maxXor = 0;
    shared_ptr<TrieNode> node = root;
    for (int i = maxBit; i >= 0; --i) {
      const int bit = num >> i & 1;
      const int toggleBit = bit ^ 1;
      if (node->children[toggleBit] != nullptr) {
        maxXor = maxXor | 1L << i;
        node = node->children[toggleBit];
      } else if (node->children[bit] != nullptr) {
        node = node->children[bit];
      } else {  // There's nothing in the Bit Trie.
        return 0;
      }
    }
    return maxXor;
  }

 private:
  const int maxBit;
  shared_ptr<TrieNode> root = make_shared<TrieNode>();
};

class Solution {
 public:
  long long maxXor(int n, vector<vector<int>>& edges, vector<int>& values) {
    long ans = 0;
    vector<vector<int>> tree(n);
    vector<long> treeSums(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      tree[u].push_back(v);
      tree[v].push_back(u);
    }

    getTreeSum(tree, 0, -1, treeSums, values);
    const long maxSubTreeSum =
        *max_element(treeSums.begin() + 1, treeSums.end());
    const int maxBit = static_cast<int>(log2(maxSubTreeSum));
    // Similar to 421. Maximum XOR of Two Numbers in an Array
    dfs(tree, 0, -1, treeSums, BitTrie(maxBit), ans);
    return ans;
  }

 private:
  // Gets the tree sum rooted at node u.
  long getTreeSum(const vector<vector<int>>& tree, int u, int prev,
                  vector<long>& treeSums, const vector<int>& values) {
    long treeSum = values[u];
    for (const int v : tree[u])
      if (v != prev)
        treeSum += getTreeSum(tree, v, u, treeSums, values);
    treeSums[u] = treeSum;
    return treeSum;
  }

  void dfs(const vector<vector<int>>& tree, int u, int prev,
           const vector<long>& treeSums, BitTrie&& bitTrie, long& ans) {
    for (const int v : tree[u]) {
      if (v == prev)
        continue;
      // Preorder to get the ans.
      ans = max(ans, bitTrie.getMaxXor(treeSums[v]));
      // Recursively call on the subtree rooted at node v.
      dfs(tree, v, u, treeSums, std::move(bitTrie), ans);
      // Postorder insert the tree sum rooted at node v.
      bitTrie.insert(treeSums[v]);
    }
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
class TrieNode {
  public TrieNode[] children = new TrieNode[2];
}

class BitTrie {
  public BitTrie(int maxBit) {
    this.maxBit = maxBit;
  }

  public void insert(long num) {
    TrieNode node = root;
    for (int i = maxBit; i >= 0; --i) {
      final int bit = (int) (num >> i & 1);
      if (node.children[bit] == null)
        node.children[bit] = new TrieNode();
      node = node.children[bit];
    }
  }

  public long getMaxXor(long num) {
    long maxXor = 0;
    TrieNode node = root;
    for (int i = maxBit; i >= 0; --i) {
      final int bit = (int) (num >> i & 1);
      final int toggleBit = bit ^ 1;
      if (node.children[toggleBit] != null) {
        maxXor = maxXor | 1L << i;
        node = node.children[toggleBit];
      } else if (node.children[bit] != null) {
        node = node.children[bit];
      } else { // There's nothing in the Bit Trie.
        return 0;
      }
    }
    return maxXor;
  }

  private int maxBit;
  private TrieNode root = new TrieNode();
}

class Solution {
  public long maxXor(int n, int[][] edges, int[] values) {
    List<Integer>[] tree = new List[n];
    long[] treeSums = new long[n];

    for (int i = 0; i < n; ++i)
      tree[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      tree[u].add(v);
      tree[v].add(u);
    }

    getTreeSum(tree, 0, -1, treeSums, values);
    final long maxSubTreeSum = getMaxSubTreeSum(treeSums);
    final int maxBit = (int) (Math.log(maxSubTreeSum) / Math.log(2));
    // Similar to 421. Maximum XOR of Two Numbers in an Array
    dfs(tree, 0, -1, treeSums, new BitTrie(maxBit));
    return ans;
  }

  private long ans = 0;

  // Gets the tree sum rooted at node u.
  private long getTreeSum(List<Integer>[] tree, int u, int prev, long[] treeSums, int[] values) {
    long treeSum = values[u];
    for (final int v : tree[u])
      if (v != prev)
        treeSum += getTreeSum(tree, v, u, treeSums, values);
    treeSums[u] = treeSum;
    return treeSum;
  }

  private long getMaxSubTreeSum(long[] treeSums) {
    long maxSubTreeSum = 0;
    for (int i = 1; i < treeSums.length; ++i)
      maxSubTreeSum = Math.max(maxSubTreeSum, treeSums[i]);
    return maxSubTreeSum;
  }

  private void dfs(List<Integer>[] tree, int u, int prev, long[] treeSums, BitTrie bitTrie) {
    for (final int v : tree[u]) {
      if (v == prev)
        continue;
      // Preorder to get the ans.
      ans = Math.max(ans, bitTrie.getMaxXor(treeSums[v]));
      // Recursively call on the subtree rooted at node v.
      dfs(tree, v, u, treeSums, bitTrie);
      // Postorder to insert the tree sum rooted at node v.
      bitTrie.insert(treeSums[v]);
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class TrieNode:
  def __init__(self):
    self.children: list[TrieNode | None] = [None] * 2


class BitTrie:
  def __init__(self, maxBit: int):
    self.maxBit = maxBit
    self.root = TrieNode()

  def insert(self, num: int) -> None:
    node = self.root
    for i in range(self.maxBit, -1, -1):
      bit = num >> i & 1
      if not node.children[bit]:
        node.children[bit] = TrieNode()
      node = node.children[bit]

  def getMaxXor(self, num: int) -> int:
    maxXor = 0
    node = self.root
    for i in range(self.maxBit, -1, -1):
      bit = num >> i & 1
      toggleBit = bit ^ 1
      if node.children[toggleBit]:
        maxXor = maxXor | 1 << i
        node = node.children[toggleBit]
      elif node.children[bit]:
        node = node.children[bit]
      else:  # There's nothing in the Bit Trie.
        return 0
    return maxXor


class Solution:
  def maxXor(self, n: int, edges: list[list[int]], values: list[int]) -> int:
    ans = 0
    tree = [[] for _ in range(n)]
    treeSums = [0] * n

    for u, v in edges:
      tree[u].append(v)
      tree[v].append(u)

    # Gets the tree sum rooted at node u.
    def getTreeSum(u: int, prev: int) -> int:
      treeSum = values[u] + sum(getTreeSum(v, u) for v in tree[u] if v != prev)
      treeSums[u] = treeSum
      return treeSum

    def dfs(u: int, prev: int, bitTrie: BitTrie) -> None:
      nonlocal ans
      for v in tree[u]:
        if v == prev:
          continue
        # Preorder to get the ans.
        ans = max(ans, bitTrie.getMaxXor(treeSums[v]))
        # Recursively call on the subtree rooted at node v.
        dfs(v, u, bitTrie)
        # Postorder to insert the tree sum rooted at node v.
        bitTrie.insert(treeSums[v])

    getTreeSum(0, -1)
    maxBit = int(math.log2(max(treeSums[1:])))
    # Similar to 421. Maximum XOR of Two Numbers in an Array
    dfs(0, -1, BitTrie(maxBit))
    return ans