거리가 K 이하인 정점 쌍
레벨 MC · 코딩 · JavaScript · 목표 시간 45분 · 게시일 2026-11-05
정점 n개(0번부터 n-1번)짜리 트리의 간선 edges([u, v, 길이])와 정수 k가 주어진다. 두 정점 사이 거리는 트리에서 둘을 잇는 경로의 길이 합이다. 거리가 k 이하인 정점 쌍 {u, v} (u ≠ v, 순서 없음)의 개수를 구하시오.
n은 1 이상 20,000 이하, 간선 길이는 1 이상 1,000 이하, k는 0 이상 10^9 이하이다. 정점마다 트리 전체를 탐색하는 방법으로는 시간 안에 끝나지 않는다. 트리가 한 줄로 길게 늘어설 수 있으니 깊은 재귀는 피하시오.
예제
solve(5, [[0,1,1],[1,2,2],[1,3,3],[3,4,1]], 3) solve(1, [], 5) solve(3, [[0,1,4],[1,2,4]], 4)