레이팅 미적용설명
\(N\)개의 마을이 \(N-1\)개의 양방향 길로 연결된 트리 형태의 나라가 있다. 각 길에는 양의 정수 길이가 있다.
두 마을 사이의 거리는 둘을 잇는 유일한 경로 위 길이의 합이다. 거리가 정확히 \(K\)인 서로 다른 마을 쌍 \((u, v)\) (\(u
\(O(N^2)\) 풀이는 통과할 수 없으며, 센트로이드 분할이 필요하다.
제약
\(1 \le N \le 100{,}000\)
\(1 \le K \le 10^{12}\)
\(1 \le w \le 10^6\)
\(1 \le a, b \le N\)
입력 형식
첫 줄에 \(N\)과 \(K\)가 주어진다.
다음 \(N-1\)줄에 각 길의 정보 \(a\), \(b\), \(w\)가 주어진다.
출력 형식
거리가 정확히 \(K\)인 마을 쌍의 개수를 출력한다.
예제 1
입력
4 2
2 1 1
3 1 2
4 2 1
출력
2설명
거리: (1,2)=1,(1,3)=2,(1,4)=2,(2,3)=3,(2,4)=1,(3,4)=4. 거리가 정확히 2인 쌍은 (1,3),(1,4)로 2개.
예제 2
입력
4 2
2 1 1
3 2 1
4 3 1
출력
2설명
길이 1짜리 사슬. 거리가 정확히 2인 쌍은 (1,3),(2,4)로 2개.
문제 정보
riseoj 작성
출처 Original
태그