레이팅 미적용농부 존과 동료 농부들은 끔찍한 소 전염병 COWVID-19가 농장들 사이에 퍼지는 것을 막기 위해 쉬지 않고 일하고 있다.
그들은 함께 \(N\)개의 농장(\(1 \leq N \leq 10^5\))을 관리하고 있으며, 농장들은 편의상 \(1 \ldots N\)으로 번호가 매겨져 있다. 농장들은 \(N-1\)개의 도로로 연결되어 있어서, 어떤 농장이든 농장 1에서 도로들을 따라 도달할 수 있다.
안타깝게도 농장 1의 소 한 마리가 방금 COWVID-19 양성 판정을 받았다. 그 농장의 다른 소들이나 다른 농장의 소들은 아직 병에 걸리지 않았다. 하지만 이 병의 전염성을 잘 아는 농부 존은 매일 다음 두 가지 좋지 않은 일 중 정확히 하나가 일어날 것으로 예상한다.
(1) 한 농장에서 "슈퍼전파" 사건이 발생하여 그 농장의 COWVID-19에 걸린 소의 수가 두 배가 된다.
(2) COWVID-19에 걸린 소 한 마리가 도로를 따라 한 농장에서 인접한 농장으로 이동한다.
농부 존은 전염병이 얼마나 빨리 퍼질지 걱정하고 있다. 모든 농장에 병에 걸린 소가 적어도 한 마리씩 있게 될 수 있는 최소 일수를 구해 농부 존을 도와주자.
문제 제공: Dhruv Rohatgi
배점
- 테스트 케이스 1-4에서는 (농장 \(1\) 자신을 제외한) 모든 농장이 농장 1과 직접 연결되어 있다.
- 테스트 케이스 5-7에서는 농장 \(2\ldots N\) 각각에 인접한 도로가 최대 두 개이다.
- 테스트 케이스 8-15에서는 추가 제약이 없다.
문제 제공: Dhruv Rohatgi
첫째 줄에 정수 \(N\)이 주어진다. 다음 \(N−1\)개의 줄에는 공백으로 구분된 두 정수 \(a\)와 \(b\)가 주어지며, 이는 농장 \(a\)와 \(b\)를 잇는 도로를 나타낸다. \(a\)와 \(b\)는 모두 \(1\ldots N\) 범위에 있다.
전염병이 모든 농장에 도달할 수 있게 되는 최소 일수를 출력한다.
4
1 2
1 3
1 45One possible sequence of events corresponding to this example is the following:
the number of sick cows in farm 1 doubles and then doubles again, so that after
two days, there are 4 sick cows in farm 1. In each of the next 3 days, a sick
cow travels from farm 1 to each of farms 2, 3, and 4 respectively. After 5
days, at least 1 sick cow exists at each farm.
riseoj 작성
출처 올림피아드 > USACO > 2020-2021 > December > Silver