GREEDY APPROACH (C++) BEATS 100 %
Intuition\n Describe your first thoughts on how to solve this problem. \n\nFIRST INTUITION : The Moment One Reads XOR, These Properties Should Strike One\'s Bra
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n**FIRST INTUITION** : The Moment One Reads XOR, These Properties Should Strike One\'s Brain Immediately.\n\n1. a ^ a = 0.\n2. a ^ 0 = a.\n3. a ^ b = b ^ a. (Would Be Our Master-Stroke For XOR On Edges)\n\nIn This Entire Question, We Will Play With These Properties.\n\n**SECOND INTUITION** : Now, Second Part Demands For Maximum Sum. Reading This Brings Two Algorithm Paradigm Mainly To Any Coder\'s Mind :- DP And Greedy Approach.\n\nCan Be Solved Using DP As Well, But I Would Like To Be Greedy Here XD !!\n\n# Approach\n<!-- Describe your approach to solving the problem. --> \n1. Keep Count Of Nodes Whose Values Can Be Increased By XOR.\n\n2. If They Are Even, We Can Pair Them Up. (XOR IS COMMUTATIVE, Hence We Can Again XOR On Adjacent Edge To Neutralise The Decreament Of Other Node\'s Value) :- **PROPAGATION OF XOR IN TREE/GRAPH.**\n\n3. In Case Count Is Odd -> *MOYE MOYE* (One Individual Node Is Remaining). Now, It\'s Time To Be Greedy And Greed Leads To Sacrifice. Find The Sacrificial Lamb (Whose Loss Won\'t Hurt Our Maximum Sum As Compared To Others) In The Entire Tree.\n\n4. In Case We Can Pair, No Need To Sarifice :- Return The Sum.\n\n5. In Case We Can\'t, Return (Sum - Sacrifice).\n\nPLEASE UPVOTE IF HELPED.. FEEL FREE TO ASK IN COMMENT SECTION.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ --> \n$$O(N)$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ --> \n$$O(1)$$\n# Code\n```\n#define ll long long\n\nclass Solution {\npublic:\n    long long maximumValueSum(vector<int> &nums, int k, vector<vector<int>> &edges) {\n        \n        // Count The Node Values To Be Increased.\n        ll sum = 0, count = 0, sacrifice = INT_MAX;\n\n        for (auto x : nums) {\n\n            // XOR Increases The Value.\n            if ((x ^ k) > x) {\n\n                sum += x ^ k;\n                count++;\n\n                // Some Node Value Would Be Decreased, And We Need To Minimise It.\n                sacrifice = min (sacrifice, (ll) (x ^ k) - x);\n            }\n\n            else {\n\n                sum += x;\n                sacrifice = min (sacrifice, (ll) x - (x ^ k));\n            }\n        }\n\n        // Even Counts Of Node Values (Pair Nodes) -> XOR Operation On Edges May Propagate In Tree.\n        // Simply, Return The Sum.\n\n        if (count % 2 == 0)\n            return sum;\n        \n        // Odd Count Of Node Values (One Individual Node) -> One Node Has To Sacrifice.\n        // Sacrifice :- Either Remain Same Or Decrease Its Value After XOR.\n        // Return :- Greedy / Most Optimal Sum We Wish To Obtain - Sacrifice.\n\n        return sum - sacrifice;\n    }   \n};\n```
['C++']