C++ || Greedy Solution || Visualized || Comprehensive explanation
Welcome to a comprehensive solution which will leave all your doubts cleared. \n\n# Intuition\n\nThere are two things we need to keep in mind in this problem\n-
Welcome to a comprehensive solution which will leave all your doubts cleared. \n\n# Intuition\n\nThere are two things we need to keep in mind in this problem\n- `XOR` and `Tree`\n- The tree is connected, which means we can reach any node from any other node freely. There always exists a path between any two nodes.\n- ` a ^ b ^ b = a ` --> The important property of `XOR`.\n\nLet us consider two examples to figure out how can we use the above two properties to maximise our results.\n\n\n# Example 1:\n\n    The node is in the form : (nodeName, nodeValue)\n    Let k = 4 -> 100 in binary\n\n        (e,4)   \n          |\n        (a,3)___(b,2)\n          |       |\n        (c,6)   (d,4)\n\n    The optimal nodes which can be applied xor with k are a and b as\n    other nodes will give a lesser value when applied xor with k.\n    a and b when xorred with k will give a greater value, thereby \n    increasing the total sum of the tree nodes\n    \n    Hence pick the edge a-b and apply xor with k to both a and b to \n    increase the value of a and b to maximise the sum.\n\n# Example 2:\n\n    The node is in the form : (nodeName, nodeValue)\n    Let k = 4 -> 100 in binary\n\n        (e,4)   \n          |\n        (a,3)___(b,4)\n          |       |\n        (c,6)   (d,6)___(e,2)\n\n    Here the optimal nodes are a and e. There is no direct edge\n    between them to apply the xor operation on them. \n\n    But consider the following path where we apply xor operation to \n    every edge in the path:\n\n        a -> b -> d -> e\n    \n    The resulting xor operations are: (a^k, b^k), (b^k, d^k), (d^k, e^k)\n    If you look carefully b and d has been xored twice which leaves us \n    b and d with it\'s initial value.\n    \n- Hence we can conclude that in any path between two nodes `x` and `y`, all the intermediate nodes will be xorred twice and have no effect in their values at the end except for `x` and `y` which will be xorred only once with `k`.\n- The above conclusion is the most important part of the solution, so if you have not understood it please read it again.\n\n# Now we can start building up our solution\n\n- If there are any two nodes, whose values can be increased by applying the xor operation with `k`, no matter where the two nodes are present in the tree, we can exactly apply the xor operations to only these two nodes as per the conclusion we got from the previous examples.\n- Hence if the number of nodes whose values can be increased by applying xor operation with `k` are `even` in number, then we can apply the xor operation to every pair of nodes using the above approach.\n- If the number of such nodes are `odd` in number, then we won\'t be able to apply the operation to one of the nodes whose value can be increased by xor with `k`.\n- In such case we must either include another node among the nodes whose values on applying xor with `k` decreases to pair it with the remaining one node whose value can be increased by xor with `k`. \n- An alternative option would be to let go of the remaining one node by without trying to apply the xor operation on it.\n\n# Consider the following examples for better understanding\n\n             ---------(X)------\n            /          |       \\\n           /           |        \\\n        (O)           (O)       (O)\n       /   \\           |           \\\n      /     \\          |            \\          \n    (X)     (O)       (O)           (X)\n                       /            /\n                      /            / \n                    (X)          (O)\n\n    Nodes marked "X" are the ones whose values can be increased by \n    applying the xor operation with k, where "O" are the nodes whose \n    values cannot be increased by the given operation. \n\n    We can see that the number of "X" nodes above is even in number\n    hence we can pair each of them into groups of 2 and apply the xor\n    operation along their paths to increase their values.\n\n    Note again that by applying the xor operation accross all the edges\n    in a path between two nodes, only the end two nodes would be\n    affected as all intermediate nodes would be xorred twice and the\n    xor operation would cancel out.\n\n    ____________________________________________________________________\n\n             ---------(X)------\n            /          |       \\\n           /           |        \\\n        (O)           (O)       (O)\n       /   \\           |           \\\n      /     \\          |            \\          \n    (X,*)   (O)       (O)           (O,*)\n                       /            /\n                      /            / \n                    (X)          (O)\n\n    Here the "X" nodes are odd in number, due to which we won\'t be able\n    to apply the xor operation to every pair of nodes as one node would\n    be left out.\n\n    We can either pair that left out node with another "O" node though \n    xor operation on "O" will reduce its value, but if the "X" node can \n    increase the sum substantially, then it would be a good tradeoff.\n\n    Alternatively we can let go of the left out "X" node without \n    applying the xor operation, which may give us the optimal answer\n\n    In the above tree, the "X" and "O" nodes marked with a "*" are\n    the arbitary nodes which we have to include in the xor operation or\n    exclude from the xor operation.\n\n    Now the task is to find those nodes and try including and excluding.\n    Which can be pretty easily done in O(N)\n        \n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n\n# Code\n```\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {\n\n        long long sum1 = 0;\n        long long sum2 = 0;\n        int count = 0;\n                \n        for(auto i: nums) {\n            // if the value of node can be increased with xor operation\n            // then add it to sum1 and increase the count\n            if((i ^ k) > i) {\n                sum1 += (i ^ k);\n                count++;\n            }\n            // else add it to sum2\n            else\n                sum2 += i;            \n        }\n            \n        // if the count is even, we can pair each of the nodes\n        // along their paths and increase the overall sum\n        if(count % 2 == 0)\n            return sum1 + sum2;\n    \n        // else we need to check a suitable inclusion from sum2 into sum1\n        // or a suitable exclusion from sum1 into sum2\n        long long maxi1 = 0;\n        long long maxi2 = 0;                  \n        for(auto i: nums) {\n            // if value of the node can be increased with xor\n            // try removing the value from sum1 and add it to sum2\n            if((i ^ k) > i) \n                maxi1 = max(maxi1, sum1 - (i ^ k) + sum2 + i);    \n            // else try removing the value from sum2 and add it to sum1\n            else\n                maxi2 = max(maxi2, sum1 + (i ^ k) + sum2 - i);                \n        }\n\n        return max(maxi1, maxi2);\n    }\n};\n```\n
['Greedy', 'Bit Manipulation', 'Tree', 'C++']