Cowntagion

시간 제한1초메모리 제한512 MB

요약

1번 농장을 뿌리로 하는 트리에서 매일 한 농장의 감염된 소 수를 두 배로 늘리거나 감염된 소 한 마리를 인접 농장으로 옮길 수 있을 때, 모든 농장에 감염된 소가 생기기까지 필요한 최소 일수를 구한다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 그리디, 수학
정답자: 아직 제출이 없습니다

문제

Farmer John과 동료 농부들은 농장들에 퍼지는 무서운 소 질병 COWVID-19의 확산을 막기 위해 쉬지 않고 일해 왔다.

그들은 $N$ 개의 농장( $1 \leq N \leq 10^5$ )을 관리하며, 농장에는 $1 \ldots N$ 의 번호가 붙어 있다. 농장들은 $N-1$ 개의 도로로 연결되어 있고, 어떤 농장에서든 도로를 따라가면 농장 1에 도달할 수 있다.

안타깝게도 농장 1의 소 한 마리가 방금 COWVID-19 양성 판정을 받았다. 그 농장의 다른 소들과 다른 농장의 소들은 아직 병에 걸리지 않았다. 하지만 전염성이 강한 병이라는 것을 아는 Farmer John은 매일 다음 두 사건 중 정확히 하나가 일어난다고 예상한다.

한 농장에서 "슈퍼전파자" 사건이 일어나 그 농장에서 COWVID-19에 걸린 소의 수가 두 배가 된다.
COWVID-19에 걸린 소 한 마리가 도로를 따라 인접한 농장으로 이동한다.

Farmer John은 발병이 얼마나 빠르게 퍼질 수 있는지 걱정한다. 모든 농장에 병에 걸린 소가 적어도 한 마리씩 있게 되는 데 걸릴 수 있는 최소 일수를 구해 그를 도와주자.

입력

첫째 줄에 정수 $N$ 이 주어진다. 다음 $N−1$ 개 줄에 농장 $a$ 와 $b$ 를 잇는 도로를 나타내는 두 정수 $a$ , $b$ 가 공백으로 구분되어 주어진다. $a$ 와 $b$ 는 모두 $1\ldots N$ 범위에 있다.

출력

발병이 모든 농장에 도달할 수 있는 최소 일수를 출력한다.

예제1

예제 1
입력
```
4
1 2
1 3
1 4
```
예상 출력
```
5
```