시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 108 | 50 | 48 | 47.525% |
어떤 PCB (Printed Circuit Board)에는 노드 $N$개가 있으며, 저항 $N-1$개가 그 사이를 사이클 없이 연결하고 있다.
우리는 PCB의 정보가 주어질 때, 두 가장자리 노드를 연결해 얻을 수 있는 가장 큰 저항값과 가장 작은 저항값을 구할 것이다. 이때 가장자리 노드란 저항 한 개만 연결된 노드이다.
위 그림에서 두 가장자리 노드를 연결하는 가장 큰 저항값과 가장 작은 저항값을 찾으면 아래와 같은 그림이 나온다.
위 그림은 두 가장자리 노드를 연결하는 가장 큰 저항값을 만드는 데 사용되는 저항이 있는 부분에 빨간색으로 나타낸 것이다. 이때 회로에서 만든 가장 큰 저항값은 $20 \Omega$이다.
위 그림은 두 가장자리 노드를 연결하는 가장 작은 저항값을 만드는 데 사용되는 저항이 있는 부분에 나타낸 것이다. 이때 회로에서 만든 가장 작은 저항값은 $9 \Omega$이다.
PCB에서 두 가장자리 노드를 연결해 얻을 수 있는 최대 저항과 최소 저항을 구하는 프로그램을 작성하시오.
첫 번째 줄에 노드의 개수 $N$이 정수로 주어진다. $(2 \le N \le 100\,000)$
그다음 $N-1$줄에 걸쳐 각 줄에는 간선의 정보로 세 정수 $p$, $q$, $w$가 공백으로 구분되어 주어진다. $(0 \le p, q < N,\ p ≠ q,\ 1 \le w \le 10\,000)$
$p$와 $q$는 저항이 연결하는 노드의 번호이고, $w$는 저항의 값이다. (단위는 $\Omega$)
두 가장자리 노드를 연결하는 가장 큰 저항값과 가장 작은 저항값을 한 줄에 하나씩 순서대로 출력한다.
10 0 1 2 1 2 4 2 3 2 3 4 1 2 7 7 5 6 2 6 7 1 7 8 5 8 9 2
20 9
위 그림과 같은 상황이다.
그림에 있는 저항의 값은 실제와 다르다.
University > 한양대학교 > 제8회 한양대학교 프로그래밍 경시대회 > Advanced Division H번