왕국의 도로망
플래티넘 I의견: 0
왕국에는 \(N\)개의 도시가 있고, 이들은 \(N-1\)개의 양방향 도로로 연결되어 있어 어떤 두 도시 사이에도 정확히 하나의 경로가 존재한다. 각 도로에는 길이가 있다.
두 도시 \(u < v\) 사이의 거리는 두 도시를 잇는 유일한 경로 위 도로 길이의 합이다. 거리가 \(K\) 이하인 서로 다른 도시 쌍 \((u, v)\)의 개수를 구하여라.
도시 수가 매우 크므로 모든 쌍을 직접 확인하는 \(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\)가 주어지며, 이는 도시 \(a\)와 \(b\)를 잇는 길이 \(w\)의 도로를 의미한다.
거리가 \(K\) 이하인 도시 쌍의 개수를 한 줄에 출력한다.
4 3
2 1 3
3 1 1
4 3 1
4거리: (1,2)=3, (1,3)=1, (1,4)=2, (2,3)=4, (2,4)=5, (3,4)=1. 이 중 거리가 3 이하인 쌍은 (1,2),(1,3),(1,4),(3,4)로 4개이다.
5 5
2 1 2
3 2 2
4 3 2
5 4 2
7일렬로 늘어선 도시. 인접 거리 2, 한 칸 건너 4 (5 이하). 거리 5 이하인 쌍은 인접(거리2) 4쌍 + 두 칸(거리4) 3쌍 = 7쌍이다.
다이아몬드 Iriseoj 작성
출처 Original
평가 및 의견
왕국의 도로망
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
왕국의 도로망