6188 : 트리 분할
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
가중치가 있는 트리에서 모든 노드 쌍 (u, v) (u < v) 중, 두 노드를 잇는 경로의 가중치 합이 K 이하인 쌍의 개수를 구하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)과 임계값 K (1 ≤ K ≤ 1,000,000)가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v, w가 주어집니다.
둘째 줄부터 N-1개의 줄에 트리 간선 정보 u, v, w가 주어집니다.
출력 설명
경로 가중치 합이 K 이하인 노드 쌍 (u, v) (u < v)의 개수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 10
1 2 5
1 3 4
3 4 6
3 5 2
출력 예시
COPY
복사되었습니다!
복사되었습니다!
8