R00442
적당한 거리의 우체국
플래티넘 I레이팅
의견: 0
설명
\(N\)개의 도시가 트리로 연결되어 있다. 각 도로는 양의 길이를 가진다.
두 도시 사이 거리가 구간 \([L, R]\) 안에 드는 서로 다른 도시 쌍의 개수를 구하여라. 즉 거리가 \(L\) 이상 \(R\) 이하인 쌍의 수이다.
센트로이드 분할로 '거리 \(\le x\)인 쌍의 수'를 두 번 구해 차를 취하면 된다.
제약
\(1 \le N \le 100{,}000\)
\(1 \le L \le R \le 10^{12}\)
\(1 \le w \le 10^6\)
\(1 \le a, b \le N\)
입력 형식
첫 줄에 \(N\), \(L\), \(R\)이 주어진다.
다음 \(N-1\)줄에 \(a\), \(b\), \(w\)가 주어진다.
출력 형식
거리가 \([L, R]\)에 속하는 도시 쌍의 개수를 출력한다.
예제 1
입력
4 2 4
2 1 2
3 1 3
4 2 2
출력
4설명
거리: (1,2)=2,(1,3)=3,(1,4)=4,(2,3)=5,(2,4)=2,(3,4)=7. [2,4]에 드는 쌍은 (1,2),(1,3),(1,4),(2,4)로 4개.
예제 2
입력
5 2 3
2 1 1
3 2 1
4 3 1
5 4 1
출력
5설명
사슬에서 거리 2 또는 3인 쌍: 거리2가 3쌍, 거리3이 2쌍, 합 5쌍.
문제 정보
riseoj 작성
출처 Original
태그
평가 및 의견
적당한 거리의 우체국
개요
Log in to rate problems.
개별 의견
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
적당한 거리의 우체국
게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다.
로그인하고 제출하기