Funcia
Lv.4centroid-decompositiondivide-and-conquertreetwo-pointers

거리가 K 이하인 마을 쌍

메모리 제한
256 MB
정확성 시간 제한
10000 ms
푼 사람
0
0

마을 n개가 n-1개의 양방향 도로로 이어져 있고, 어느 두 마을 사이에도 경로가 정확히 하나 있습니다(트리). 마을 번호는 0부터 n-1까지이며, edges[i] = [u, v, w]는 마을 u와 v를 잇는 길이 w인 도로입니다.

두 마을 사이의 거리는 둘을 잇는 유일한 경로의 도로 길이 합입니다. 거리가 k 이하인 마을 쌍 {a, b}(a ≠ b, 순서 무관)의 개수를 반환하세요.

입출력 예

nedgeskresult
5[[0, 1, 2], [1, 2, 3], [1, 3, 1], [3, 4, 4]]46
3[[0, 1, 5], [1, 2, 5]]40
4[[0, 1, 1], [0, 2, 1], [0, 3, 1]]26

입출력 예 설명

예 1 — 거리가 4 이하인 쌍은 {0,1}(2), {0,3}(3), {1,2}(3), {1,3}(1), {2,3}(4), {3,4}(4) 여섯 개입니다. {0,2}는 5, {1,4}는 5라서 제외됩니다.

예 2 — 가장 가까운 쌍도 거리가 5입니다.

예 3 — 별 모양 트리에서 모든 쌍의 거리가 2 이하입니다.

효율성

이 문제에는 효율성 테스트가 있습니다. 제한 사항의 입력 크기를 보고 필요한 시간 복잡도를 직접 판단하세요.

함수 시그니처

solution(n: int, edges: int[][], k: int) → long

제한 사항

  • 1≤1 \le n ≤50,000\le 50{,}000
  • edges.length == n −1- 1, edges[i] = [u, v, w], 0≤u,v<0 \le u, v < n, 1≤w≤10,0001 \le w \le 10{,}000
  • 주어지는 도로는 트리를 이룹니다.
  • 0≤0 \le k ≤109\le 10^9
  • 답이 32비트 정수 범위를 넘을 수 있습니다.

기대 복잡도

시간
O(N log^2 N)
공간
O(N)

입출력 예

nedgesk기대 출력
5[[0,1,2],[1,2,3],[1,3,1],[3,4,4]]46
3[[0,1,5],[1,2,5]]40
4[[0,1,1],[0,2,1],[0,3,1]]26

힌트

힌트

모든 마을에서 DFS를 하면 O(n2)O(n^2)입니다. k가 크면 가지치기도 소용이 없습니다.

센트로이드 분할

트리의 센트로이드(지우면 남는 조각이 모두 n/2n/2 이하가 되는 정점) c를 고르면, 모든 경로는 둘 중 하나입니다.

  1. c를 지나는 경로
  2. c를 지운 뒤 남은 한 조각 안에만 있는 경로 → 그 조각에서 재귀적으로 셉니다.

센트로이드로 자르면 조각 크기가 매번 절반 이하가 되므로 재귀 깊이는 O(log⁡n)O(\log n)이고, 각 깊이에서 전체 작업량은 O(nlog⁡n)O(n \log n)입니다.

c를 지나는 쌍 세기

  • c에서 모든 정점까지의 거리를 구해 정렬하고, 투 포인터로 "합이 k 이하인 쌍"을 셉니다(c 자신은 거리 0으로 포함).
  • 이렇게 세면 같은 조각 안의 두 정점도 섞여 들어가는데, 그 쌍의 실제 경로는 c를 지나지 않습니다. 조각마다 같은 방식으로 센 값을 빼 주면 정확해집니다.

재귀 대신 명시적인 스택으로 구현하면 깊은 트리에서도 안전합니다.

복잡도 목표

O(nlog⁡2n)O(n \log^2 n)입니다. 정점마다 DFS를 하는 풀이는 효율성 테스트에서 시간 초과가 납니다.

언어별 시간 제한

언어효율성 시간 제한
C (GCC, gnu17)226 ms추정
C++ (GCC, gnu++23)226 ms도출됨
Python 3.131966 ms도출됨
Java 252196 ms도출됨
Kotlin 2.4 (JVM)1452 ms추정
C# 14 (.NET 10)1452 ms추정

테스트 그룹

그룹배점테스트 수공개 범위
sample03입력·출력 공개
correctness4012판정만
performance605판정만
에디터 불러오는 중…

아직 결과가 없습니다. 실행 또는 제출하세요.