[2024] day 141. Leetcode 3068. Find the Maximum Sum of Node Values

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 19일 (일)
Leetcode daily problem

3068. Find the Maximum Sum of Node Values

https://leetcode.com/problems/find-the-maximum-sum-of-node-values/?envType=daily-question&envId=2024-05-19

Problem

0부터 n - 1까지 번호가 매겨진 n개의 노드가 있는 무방향 트리가 있다. 길이가 n - 1인 0 인덱스 2D 정수 배열 가장자리가 제공된다.
여기서 edge[i] = [ui, vi]는 트리의 노드 ui와 vi로 사이에 가장자리가 있음을 나타낸다.
추가로 양의 정수 k와 길이가 n인 음이 아닌 정수로 구성된 0 인덱스 배열이 제공되는데 여기서 nums[i]는 노드 번호 i의 값을 나타낸다.

Alice는 트리 노드 값의 합이 최대가 되기를 원하며, 이를 위해 Alice는 트리에서 다음 작업을 여러 번(0 포함) 수행할 수 있다.

• 노드 u와 v를 연결하는 모서리 [u, v]를 선택하고 다음과 같이 해당 값을 업데이트한다.
  -> 숫자[u] = 숫자[u] XOR k
  -> 숫자[v] = 숫자[v] XOR k

Alice가 여러 번 작업을 수행하여 얻을 수 있는 값의 가능한 최대 합계를 반환한다.

Solution

XOR operation

Code

Complexicity

시간 복잡도

공간 복잡도