N개의 노드와 N-1개의 가장자리가 있는 트리로 표현되는 국가를 고려하십시오. 이제 각 노드는 마을을 나타내고 각 가장자리는 도로를 나타냅니다. N-1 크기의 소스와 목적지의 두 가지 숫자 목록이 있습니다. 그들에 따르면 i 번째 도로는 소스[i]와 목적지[i]를 연결합니다. 그리고 도로는 양방향입니다. 또한 크기 N의 인구라고 하는 또 다른 숫자 목록이 있습니다. 여기서 인구[i]는 i번째 마을의 인구를 나타냅니다. 우리는 몇몇 마을을 도시로 업그레이드하려고 합니다. 그러나 두 도시는 서로 인접해서는 안 되며 마을에 인접한 모든 노드는 도시여야 합니다(모든 도로는 도시와 도시를 연결해야 함). 그래서 우리는 모든 도시의 가능한 최대 인구를 찾아야 합니다.
따라서 입력이 source =[2, 2, 1, 1] dest =[1, 3, 4, 0] population =[6, 8, 4, 3, 5]와 같으면 출력은 15가 됩니다. 도시 0, 2, 4를 업그레이드하여 6 + 4 + 5 =15의 인구를 얻을 수 있기 때문입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- adj :=source 및 dest를 사용하여 그래프의 인접 목록 만들기
- dfs() 함수를 정의합니다. x 소요됩니다. 선택
- x가 보이면
- 0을 반환
- 표시된 대로 x 표시
- ans :=0
- select가 참이면
- ans :=ans + 인구[x]
- adj[x]의 각 이웃에 대해 다음을 수행합니다.
- ans :=ans + dfs(이웃, 선택의 역)
- 반환
- 기본 방법에서 다음을 수행합니다.
- x :=dfs(0, 참)
- x 및 ((인구의 합) - x)의 최대값을 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
from collections import defaultdict class Solution: def solve(self, source, dest, population): adj = defaultdict(list) for a, b in zip(source, dest): adj[a].append(b) adj[b].append(a) seen = set() def dfs(x, choose): if x in seen: return 0 seen.add(x) ans = 0 if choose: ans += population[x] for neighbor in adj[x]: ans += dfs(neighbor, not choose) return ans x = dfs(0, True) return max(x, sum(population) - x) ob = Solution() source = [2, 2, 1, 1] dest = [1, 3, 4, 0] population = [6, 8, 4, 3, 5] print(ob.solve(source, dest, population))
입력
[2, 2, 1, 1], [1, 3, 4, 0], [6, 8, 4, 3, 5]
출력
15