✅ O(n) DP + Greedy Solution in C++
Intuition\nTo find the maxSum for a subtree corresponding to a node curr, we need to find the maxSum for each children of curr in two cases:\nThe operation is p
# Intuition\nTo find the maxSum for a subtree corresponding to a node `curr`, we need to find the maxSum for each children of `curr` in two cases:\nThe operation is performed on the edge between them - `withOp`\nThe operation is not performed on the edge between them - `withoutOp`\n\nThe number of nodes whose values can be changed should be even since we are operating on an edge which involves two nodes. If the number of nodes is not even, we have two options:\nEither take the least possible loss i.e. change the value of a node despite a decrease.\nOr leave the least gain i.e. undo a change which resulted in an increase.\n\n# Approach\nTo find `maxSum`, we will accumulate the maximum of two possible values for each node (parent and children) in `sum` and will count the number of favourable changes in `numChanges`. At the end, if `numChanges` is odd, we can simply subtract the least absolute difference of `withOp` and `withoutOp` (stored in `minChange`) from `sum` which will result in subtraction of either the least loss or the least gain.\n\nThe initial value of `curr` depends on whether the operation was performed on the edge to its parent. A boolean argument `c` indicates whether the operation was performed or not.\n\nTo optimize the solution, we will store the `maxSum` values for each node in a `dp` array to avoid repeated calculations.\n\nAlso, it should be noted that we can take any of the nodes as the root of the tree, it won\'t make any difference.\n\n# Complexity\n- Time complexity: `O(N)`\nwhere `N` is the number of nodes in the tree.\nSince, we traverse the whole tree and visit each edge. The number of edges is `N - 1`.\n\n\n- Space complexity: `O(N * E\')`\nwhere `E\'` is the average number of edges for each node.\n\n# Code\n```\nclass Solution {\n    vector<vector<long long>> dp;\n    long long maxSum (int curr, bool c, int parent, vector<int> & nums, int k, vector<vector<int>> & adjList) {\n        if (dp[curr][c] != -1)\n            return dp[curr][c];\n        int val = (c ? nums[curr] ^ k : nums[curr]);\n        long long sum = max(val ^ k, val);\n        int numChanges = (val ^ k) > val, minChange = abs((val ^ k) - val);\n        for (int nbr : adjList[curr]) {\n            if (nbr == parent)\n                continue;\n            long long withOp = maxSum(nbr, true, curr, nums, k, adjList);\n            long long withoutOp = maxSum(nbr, false, curr, nums, k, adjList);\n            sum += max(withOp, withoutOp);\n            // cout << nbr << ": " << sum << endl;\n            numChanges += (withOp > withoutOp);\n            minChange = min(minChange, (int)abs(withOp - withoutOp));\n        }\n        dp[curr][c] = (sum - (numChanges % 2 ? minChange : 0));\n        // cout << "dp[" << curr << "," << c << "] = " << dp[curr][c] << endl;\n        return dp[curr][c];\n    }\npublic:\n    long long maximumValueSum(vector<int> & nums, int k, vector<vector<int>> & edges) {\n        int n = nums.size();\n        vector adjList(n, vector<int>());\n        for (auto & e : edges) {\n            adjList[e[0]].push_back(e[1]);\n            adjList[e[1]].push_back(e[0]);\n        }\n        dp.resize(n, vector<long long>(2, -1));\n        // cout << "Ok\\n";\n        return maxSum(0, false, -1, nums, k, adjList);\n    }\n};\n```\n\nA better solution has been given by [votrubac](https://leetcode.com/votrubac/) which does not requires the use of `dp` or even the given  `edges`! You can check it out [here](https://leetcode.com/problems/find-the-maximum-sum-of-node-values/solutions/4811460/greedy-sacrifice).\n
['C++']