fork download
copy 
  1. /*
  2. QUESTION 13: Uber OA — Maximum Sum of Two Separate Subtree XORs
  3.  
  4. Problem Statement:
  5. You are given a rooted tree.
  6. Every node has an integer value.
  7.  
  8. For each node u:
  9. subtreeXor[u] is the XOR of all values in u's subtree.
  10.  
  11. Choose two nodes a and b such that their subtrees do not share any node.
  12.  
  13. Maximize:
  14. subtreeXor[a] + subtreeXor[b]
  15.  
  16. Return that maximum value.
  17.  
  18. Hard Constraints:
  19. 1 <= N <= 200000
  20. 0 <= value[i] <= 1e9
  21.  
  22. Example:
  23. values = [4, 6, 2, 9, 5]
  24. edges:
  25. 1 - 2
  26. 1 - 3
  27. 2 - 4
  28. 2 - 5
  29.  
  30. Expected Output:
  31. 14
  32.  
  33. Explanation:
  34. Choose subtree rooted at node 4 and subtree rooted at node 5.
  35. Their XOR values are 9 and 5.
  36.  
  37. Sum = 14
  38.  
  39. Brute Force:
  40. Compute subtree ranges using DFS.
  41. Try every pair of nodes.
  42. Check if their subtree intervals overlap.
  43.  
  44. Time Complexity:
  45. O(N^2)
  46.  
  47. Optimized Approach:
  48. During DFS, compute:
  49. subtreeXor[u]
  50.  
  51. Also maintain:
  52. bestSingle[u] = maximum subtree XOR inside subtree u
  53. bestPair[u] = best sum of two non-overlapping subtree XORs inside subtree u
  54.  
  55. Different child branches of the same node are automatically non-overlapping.
  56.  
  57. Time Complexity:
  58. O(N)
  59.  
  60. Space Complexity:
  61. O(N)
  62. */
  63.  
  64. #include <bits/stdc++.h>
  65. using namespace std;
  66.  
  67. class Solution {
  68. public:
  69.     vector<vector<int>> tree;
  70.     vector<int> value;
  71.  
  72.     vector<long long> subtreeXor;
  73.     vector<long long> bestSingle;
  74.     vector<long long> bestPair;
  75.  
  76.     void dfs(int u, int parent) {
  77.         subtreeXor[u] = value[u];
  78.  
  79.         for (int v : tree[u]) {
  80.             if (v == parent) continue;
  81.  
  82.             dfs(v, u);
  83.             subtreeXor[u] ^= subtreeXor[v];
  84.         }
  85.  
  86.         bestSingle[u] = subtreeXor[u];
  87.         bestPair[u] = -1;
  88.  
  89.         long long bestSeenFromPreviousChild = -1;
  90.  
  91.         for (int v : tree[u]) {
  92.             if (v == parent) continue;
  93.  
  94.             bestPair[u] = max(bestPair[u], bestPair[v]);
  95.  
  96.             if (bestSeenFromPreviousChild != -1) {
  97.                 bestPair[u] = max(bestPair[u],
  98.                                   bestSeenFromPreviousChild + bestSingle[v]);
  99.             }
  100.  
  101.             bestSeenFromPreviousChild =
  102.                 max(bestSeenFromPreviousChild, bestSingle[v]);
  103.  
  104.             bestSingle[u] = max(bestSingle[u], bestSingle[v]);
  105.         }
  106.     }
  107.  
  108.     long long maxTwoSubtreeXor(vector<int>& values, vector<vector<int>>& edges) {
  109.         int n = values.size();
  110.  
  111.         value = values;
  112.         tree.assign(n, {});
  113.  
  114.         for (auto &e : edges) {
  115.             int u = e[0] - 1;
  116.             int v = e[1] - 1;
  117.  
  118.             tree[u].push_back(v);
  119.             tree[v].push_back(u);
  120.         }
  121.  
  122.         subtreeXor.assign(n, 0);
  123.         bestSingle.assign(n, 0);
  124.         bestPair.assign(n, -1);
  125.  
  126.         dfs(0, -1);
  127.  
  128.         return bestPair[0];
  129.     }
  130. };
  131.  
  132. int main() {
  133.     Solution sol;
  134.  
  135.     vector<int> values = {4, 6, 2, 9, 5};
  136.  
  137.     vector<vector<int>> edges = {
  138.         {1, 2},
  139.         {1, 3},
  140.         {2, 4},
  141.         {2, 5}
  142.     };
  143.  
  144.     cout << sol.maxTwoSubtreeXor(values, edges) << endl;
  145.  
  146.     return 0;
  147. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
14
https://ideone.com/yP5u5M
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!