R00444
짧은 산책로의 수
플래티넘 I레이팅
의견: 0
설명
\(N\)개의 교차로가 \(N-1\)개의 길로 연결된 공원이 있다. 모든 길의 길이는 \(1\)이다.
서로 다른 두 교차로를 잇는 경로(산책로)의 길이는 지나는 길의 개수와 같다. 길이가 \(K\) 이하인 서로 다른 교차로 쌍 \((u, v)\)의 개수를 구하여라.
이는 트리 위에서 변의 개수가 \(K\) 이하인 정점 쌍을 세는 문제로, 센트로이드 분할로 해결한다.
제약
\(1 \le N \le 100{,}000\)
\(1 \le K \le N-1\)
\(1 \le a, b \le N\)
입력 형식
첫 줄에 \(N\)과 \(K\)가 주어진다.
다음 \(N-1\)줄에 길의 양 끝 교차로 \(a\), \(b\)가 주어진다.
출력 형식
길이가 \(K\) 이하인 교차로 쌍의 개수를 출력한다.
예제 1
입력
5 2
1 2
1 3
3 4
3 5
출력
8설명
변 개수가 2 이하인 쌍을 센다. 인접(거리1) 4쌍, 거리2인 쌍 (2,3),(1,4),(1,5),(4,5)로 4쌍, 합 8쌍.
예제 2
입력
5 1
2 1
3 2
4 3
5 4
출력
4설명
길이 1 이하 = 인접 쌍만. 사슬에서 인접 쌍은 4개.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
짧은 산책로의 수
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
짧은 산책로의 수
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기