정확히 K만큼 떨어진 친구
플래티넘 I의견: 0
\(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\)인 마을 쌍의 개수를 출력한다.
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개.
4 2
2 1 1
3 2 1
4 3 1
2길이 1짜리 사슬. 거리가 정확히 2인 쌍은 (1,3),(2,4)로 2개.
riseoj 작성
출처 Original
평가 및 의견
정확히 K만큼 떨어진 친구
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
정확히 K만큼 떨어진 친구