K-분할 가능한 성분의 최대 개수

2872. K-분할 가능한 최대 성분 수

난이도:어려움

주제: 트리, 깊이 우선 검색

0부터 n - 1까지 레이블이 지정된 n개의 노드가 있는 무방향 트리가 있습니다. 정수 n과 길이가 n - 1인 2차원 정수 배열 모서리가 제공됩니다. 여기서 모서리[i] = [a_i, b_i]는 노드 a_i와 노드 사이에 가장자리가 있음을 나타냅니다. b_나나무에.

또한 길이 n의 0-인덱스 정수 배열 값이 제공됩니다. 여기서 값[i]는 i^번째 노드와 연결된 값이고 정수 k입니다.

트리의 유효한 분할은 결과 구성 요소가 모두 k로 나눌 수 있는 값을 갖도록 트리에서 비어 있을 수 있는 가장자리 세트를 제거하여 얻습니다. 여기서 값은 연결된 구성 요소는 해당 노드 값의 합입니다.

유효한 분할에서 최대 구성 요소 수를 반환합니다.

예 1:

• 입력: n = 5, 가장자리 = [[0,2],[1,2],[1,3],[2,4]], 값 = [1,8,1,4 ,4], k = 6
• 출력: 2
• 설명: 노드 1을 2와 연결하는 에지를 제거합니다. 결과 분할은 다음과 같은 이유로 유효합니다.
  • 노드 1과 3을 포함하는 구성요소의 값은 값[1] 값[3] = 12입니다.
  • 노드 0, 2, 4를 포함하는 구성 요소의 값은 값[0] 값[2] 값[4] = 6입니다.
  • 다른 유효한 분할에는 2개 이상의 연결된 구성 요소가 없음을 알 수 있습니다.

예 2:

• 입력: n = 7, 가장자리 = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6] ], 값 = [3,0,6,1,5,2,1], k = 3
• 출력: 3
• 설명: 노드 0과 2를 연결하는 에지를 제거하고 노드 0과 1을 연결하는 에지를 제거합니다. 결과 분할은 다음과 같은 이유로 유효합니다.
  • 노드 0을 포함하는 구성요소의 값은 값[0] = 3입니다.
  • 노드 2, 5, 6을 포함하는 구성요소의 값은 값[2] 값[5] 값[6] = 9입니다.
  • 노드 1, 3, 4를 포함하는 구성 요소의 값은 값[1] 값[3] 값[4] = 6입니다.
  • 다른 유효한 분할에는 3개 이상의 연결된 구성 요소가 없음을 알 수 있습니다.

제약조건:

• 1 4
• edges.length == n - 1
• 가장자리[i].length == 2
• 0

  설명:

  1. 트리 구성: 트리 구조를 표현하기 위해 인접 목록을 만듭니다. 각 에지는 두 개의 노드를 연결하며 이 인접 목록을 사용하여 트리를 탐색합니다.
  2. DFS 순회: DFS 함수는 각 노드를 루트로 하는 하위 트리의 합을 재귀적으로 계산합니다. 하위 트리의 합이 k로 나누어지면 결과를 증가시키고 하위 트리를 별도의 유효한 구성 요소로 간주합니다.
  3. 하위 트리 합계 반환: 각 노드에 대해 DFS 함수는 해당 하위 트리에 대한 값의 합계를 반환합니다. 하위 트리가 k로 나누어지면 합계 0을 반환하여 가장자리를 효과적으로 "절단"하여 더 이상 상위 노드와 다시 병합되는 것을 방지합니다.
  4. 최종 확인: DFS가 끝나면 전체 트리의 합이 k로 나누어지면 유효한 구성 요소로 간주되는지 확인합니다.

  예제 연습:

  예 1:

  입력:

  • n = 5, 모서리 = [[0,2],[1,2],[1,3],[2,4]], 값 = [1,8,1,4,4], k = 6.

  DFS는 노드 0에서 시작됩니다.

  • 노드 0: 하위 트리 합계 = 1
  • 노드 2: 하위 트리 합계 = 1 1 4 = 6(6으로 나눌 수 있으므로 이 가장자리를 잘라낼 수 있음)
  • 노드 1: 하위 트리 합계 = 8 4 = 12(6으로 나눌 수 있으며 이 가장자리를 잘라냄)
  • 최종 구성품 개수 = 2.

  예 2:

  입력:

  • n = 7, 모서리 = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], 값 = [3,0 ,6,1,5,2,1], k = 3.

  DFS는 노드 0에서 시작됩니다.

  • 노드 0: 하위 트리 합계 = 3
  • 노드 2: 하위 트리 합계 = 6 2 1 = 9(3으로 나눌 수 있으며 이 가장자리를 잘라냄)
  • 노드 1: 하위 트리 합계 = 0 5 = 5(3으로 나눌 수 없음, 이 합계 병합)
  • 최종 구성품 개수 = 3.

  시간 복잡도:

  • DFS 시간 복잡도: O(n), 여기서 n은 노드 수입니다. 각 노드를 한 번씩 방문하여 각 노드에서 상수 시간 작업을 수행합니다.
  • 공간 복잡도: 인접 목록, 방문 배열 및 재귀 스택의 경우 O(n)

  따라서 전체 시간 및 공간 복잡도는 O(n)이므로 주어진 문제 제약 조건에 대해 이 접근 방식이 효율적입니다.

  연락처 링크

  이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

  이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

  • 링크드인
  • 깃허브

위 내용은 K-분할 가능한 성분의 최대 개수의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!