aboutsummaryrefslogtreecommitdiff
path: root/find_max_sum_node_val.py
blob: 80bc7d46a0e402ea28fe080a177256f4ea05f2e9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 3068. Find the Maximum Sum of Node Values

"""
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'. return the maximum possible sum of the values alice
can achieve by performing the operation any number of times.
"""


class Solution(object):
    def maximumValueSum(self, nums, k, edges):
        """
        :type nums: List[int]
        :type k: int
        :type edges: List[List[int]]
        :rtype: int
        """
        ans, c, d = 0, 0, 1 << 30
        for n in nums:
            ans += max(n, b := n ^ k)
            c ^= n < b
            d = min(d, abs(n - b))
        return ans - d * c


if __name__ == "__main__":
    obj = Solution()
    print(obj.maximumValueSum(nums=[1, 2, 1], k=3, edges=[[0, 1], [0, 2]]))
    print(obj.maximumValueSum(nums=[2, 3], k=7, edges=[[0, 1]]))
    print(
        obj.maximumValueSum(
            nums=[7, 7, 7, 7, 7, 7], k=3, edges=[[0, 1], [0, 2], [0, 3], [0, 4], [0, 5]]
        )
    )