🧠 LeetCode 풀이로 상위 1%가 될 때까지 — Day `54`

문제는 각 노드에 값이 있는 n개의 노드가 있는 트리에서 두 개의 가장자리를 제거한 후 최소 점수를 찾는 것입니다. 목표는 가장자리를 절단한 후 형성된 세 개의 개별 트리의 최대 XOR 값과 최소 XOR 값 간의 차이를 최소화하는 것입니다. 무차별 대입 접근 방식은 가능한 모든 가장자리 쌍을 시도하는 것이지만 시간 복잡도는 O(n³)입니다. 보다 최적화된 전략은 인접성 목록을 사용하여 트리를 구축하고 루트에서 깊이 우선 검색(DFS)을 수행하여 모든 노드에 대한 하위 트리 XOR을 계산하고 각 노드의 하위 트리에 속하는 노드를 추적하는 것입니다. 그런 다음 모든 노드 쌍을 반복하고 세 개의 XOR 부분을 계산하고 점수를 평가합니다. 발견된 최소 점수가 반환됩니다. Python의 코드 구현은 defaultdict를 사용하여 그래프를 작성하고 DFS 함수를 사용하여 하위 트리 XOR 및 하위 항목을 계산합니다. 해의 시간 및 공간 복잡도는 O(n²)입니다. 이 문제에서 얻을 수 있는 주요 내용은 XOR 및 트리 DP의 사용과 문제 요구 사항을 이해하는 것의 중요성입니다. 저자는 도움을 필요로 했고 처음에는 해결책을 완전히 이해하지 못했음을 인정하면서 문제를 해결한 경험을 되돌아봅니다.