Lv.4centroid-decompositiondivide-and-conquertreetwo-pointers
거리가 K 이하인 마을 쌍
- 메모리 제한
- 256 MB
- 정확성 시간 제한
- 10000 ms
- 푼 사람
- 0
마을 n개가 n-1개의 양방향 도로로 이어져 있고, 어느 두 마을 사이에도 경로가 정확히 하나 있습니다(트리). 마을 번호는 0부터 n-1까지이며, edges[i] = [u, v, w]는 마을 u와 v를 잇는 길이 w인 도로입니다.
두 마을 사이의 거리는 둘을 잇는 유일한 경로의 도로 길이 합입니다. 거리가 k 이하인 마을 쌍 {a, b}(a ≠ b, 순서 무관)의 개수를 반환하세요.
입출력 예
| n | edges | k | result |
|---|---|---|---|
5 | [[0, 1, 2], [1, 2, 3], [1, 3, 1], [3, 4, 4]] | 4 | 6 |
3 | [[0, 1, 5], [1, 2, 5]] | 4 | 0 |
4 | [[0, 1, 1], [0, 2, 1], [0, 3, 1]] | 2 | 6 |
입출력 예 설명
예 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
제한 사항
-
n edges.lengthn,edges[i] = [u, v, w],n,- 주어지는 도로는 트리를 이룹니다.
-
k - 답이 32비트 정수 범위를 넘을 수 있습니다.
기대 복잡도
- 시간
- O(N log^2 N)
- 공간
- O(N)
입출력 예
| n | edges | k | 기대 출력 |
|---|---|---|---|
5 | [[0,1,2],[1,2,3],[1,3,1],[3,4,4]] | 4 | 6 |
3 | [[0,1,5],[1,2,5]] | 4 | 0 |
4 | [[0,1,1],[0,2,1],[0,3,1]] | 2 | 6 |
힌트
힌트
모든 마을에서 DFS를 하면 입니다. k가 크면 가지치기도 소용이 없습니다.
센트로이드 분할
트리의 센트로이드(지우면 남는 조각이 모두 이하가 되는 정점) c를 고르면, 모든 경로는 둘 중 하나입니다.
c를 지나는 경로c를 지운 뒤 남은 한 조각 안에만 있는 경로 → 그 조각에서 재귀적으로 셉니다.
센트로이드로 자르면 조각 크기가 매번 절반 이하가 되므로 재귀 깊이는 이고, 각 깊이에서 전체 작업량은 입니다.
c를 지나는 쌍 세기
c에서 모든 정점까지의 거리를 구해 정렬하고, 투 포인터로 "합이k이하인 쌍"을 셉니다(c자신은 거리 0으로 포함).- 이렇게 세면 같은 조각 안의 두 정점도 섞여 들어가는데, 그 쌍의 실제 경로는
c를 지나지 않습니다. 조각마다 같은 방식으로 센 값을 빼 주면 정확해집니다.
재귀 대신 명시적인 스택으로 구현하면 깊은 트리에서도 안전합니다.
복잡도 목표
입니다. 정점마다 DFS를 하는 풀이는 효율성 테스트에서 시간 초과가 납니다.
언어별 시간 제한
| 언어 | 효율성 시간 제한 | |
|---|---|---|
| C (GCC, gnu17) | 226 ms | 추정 |
| C++ (GCC, gnu++23) | 226 ms | 도출됨 |
| Python 3.13 | 1966 ms | 도출됨 |
| Java 25 | 2196 ms | 도출됨 |
| Kotlin 2.4 (JVM) | 1452 ms | 추정 |
| C# 14 (.NET 10) | 1452 ms | 추정 |
테스트 그룹
| 그룹 | 배점 | 테스트 수 | 공개 범위 |
|---|---|---|---|
| sample | 0 | 3 | 입력·출력 공개 |
| correctness | 40 | 12 | 판정만 |
| performance | 60 | 5 | 판정만 |