3068: Find-the-Maximum-Sum-of-Node-Values
Hard

This problem is so cheese-able…

Basically, realise that the entire graph has n nodes and is connected with n-1 edges. Therefore, since every node is connected (with a distance of 1 to n-1 edges) for any 2 nodes, realise that if we want to XOR any 2 nodes, we can just XOR every pair between the 2 nodes.

To run through an example, let us say the nodes 1 and 4 are connected together with the formation

1 -- 2 -- 3 -- 4

Then, if we wanted to XOR both 1 and 4 ONLY, we can simply XOR:

• 1 -- 2
• 2 -- 3
• 3 -- 4

meaning, since we have XORed 2 and 3 twice, they cancel out; leaving only nodes 1 and 4 XORed once. We could inductively prove that this holds between any 2 nodes that are connected, but we leave that as an exercise for the reader. :P

Therefore, if we simply find all the values where XORing it with k would INCREASE the total sum, we are effectively able to XOR them all GIVEN we have an even number of target nodes.

If we do not have an even number of target nodes, we can either:

code

class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        long long sum = 0;
        bool even = true;
        int minPositiveDiff = INT32_MAX;
        int maxNegativeDiff = INT32_MIN;
        for (int& num : nums) {
            int difference = (num^k)-num;
            if (difference > 0) {
                sum += num^k;
                minPositiveDiff = min(minPositiveDiff, difference);
                even = !even;
            } else {
                maxNegativeDiff = max(maxNegativeDiff, difference);
                sum += num;
            }
        }
        if (!even) {
            return max(sum-minPositiveDiff, sum+maxNegativeDiff);
        }
        return sum;
    }
};

complexity