[LeetCode] 3068. Find the Maximum Sum of Node Values

https://leetcode.com/problems/find-the-maximum-sum-of-node-values/description/

leetcode - Find the Maximum Sum of Node Values

문제 유형 : 수학, 비트마스킹, 트리

문제 난이도 : Hard

 

문제

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 0-indexed 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree. You are also given a positive integer k, and a 0-indexed array of non-negative integers nums of length n, where nums[i] represents the value of the node numbered i.

Alice wants the sum of values of tree nodes to be maximum, for which Alice can perform the following operation any number of times (including zero) on the tree:

• Choose any edge [u, v] connecting the nodes u and v, and update their values as follows:
  • nums[u] = nums[u] XOR k
  • nums[v] = nums[v] XOR k

Return the maximum possible sum of the values Alice can achieve by performing the operation any number of times.

 

풀이

사실 그래프를 순회할 필요 없이, xor 연산을 하였을 때 더 큰 노드는 xor연산을 해서 누적시키고, 아니라면 그냥 누적시키면 된다.

 

그래프가 트리이기 때문에, 주어지는 간선에 관계없이, 원하는 두 쌍씩 토글시킬 수 있다.

단, 뒤집는 쌍의 수가 홀수 개라면, 어느 한 쌍을 포기하거나, 한 노드를 추가로 더 xor 토글시켜야 한다.

그렇기 때문에, 추가로 더 뒤집어서 얻는 편익과 덜 뒤집었을 때의 편익을 고려해야 한다.

만약 xor값이 더 크다면, 토글시킬 것이므로, 뒤집는 수를 하나 늘리고, xor로 더 커진만큼 더 누적시킨다. 만약 추가 토글을 포기할 시를 위해, 최소 편익을 업데이트시킨다..

더 작다면, 그 노드를 뒤집으면 손해이다. 추가 토글시켰을 때의 최소의 손해를 업데이트 시킨다.

 

만약 뒤집는 횟수가 짝수라면, 그대로 누적을 반환하고, 아니라면, 누적 - 최소편익, 누적 + 최소손해 중 더 큰 값을 반환해서 추가 토글을 시키는 것이 이득인지, 아니면 하나 덜 토클하는게 이득인지를 알아내서 반환시킨다.

 

 

코드

C++

class Solution {
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        int cnt = 0;
        long long totalSum = 0;
        int positive_Min = INT_MAX;
        int negative_Max = INT_MIN;

        for(int nodeValue : nums) {
            int nodeAfterOp = nodeValue ^ k;
            totalSum += nodeValue;
            int netChange = nodeAfterOp - nodeValue;

            if(netChange > 0) {
                positive_Min = min(netChange, positive_Min);
                totalSum += netChange;
                cnt += 1;
            } else {
                negative_Max = max(negative_Max, netChange);
            }
        }

        if(cnt % 2 == 0) {
            return totalSum;
        }

        return max(totalSum - positive_Min, totalSum + negative_Max);
    }
};