레이팅 미적용마침내 궁지에 몰린 베시는 외딴 농장에 몸을 숨겼다. 이 농장은 \(N\)개의 헛간(\(2 \leq N \leq 7 \cdot 10^4\))과 헛간들 사이를 잇는 \(N-1\)개의 양방향 터널로 이루어져 있어, 모든 헛간 쌍 사이에 유일한 경로가 존재한다. 터널이 하나뿐인 헛간은 모두 출구이다. 아침이 되면 베시는 어떤 헛간에서 모습을 드러내고 출구에 도달하려고 시도할 것이다.
하지만 베시가 어떤 헛간에서 모습을 드러내는 순간, 경찰은 그녀의 위치를 정확히 알아낼 수 있다. 그러면 몇몇 농부들이 여러 출구 헛간에서 출발하여 베시를 잡으려 할 것이다. 농부들은 베시와 같은 속도로 움직인다(즉, 각 시간 단계마다 각 농부는 한 헛간에서 인접한 헛간으로 이동할 수 있다). 농부들은 항상 베시의 위치를 알고 있고, 베시도 항상 농부들의 위치를 알고 있다. 어느 순간이든 농부가 베시와 같은 헛간에 있거나 베시와 같은 터널을 건너고 있으면 농부들은 베시를 잡는다. 반대로, 베시가 어떤 농부에게 잡히기 엄격히 이전에 출구 헛간에 도달하면 베시는 탈출한다.
베시는 어느 헛간에서 모습을 드러내야 할지 확신이 서지 않는다. \(N\)개의 각 헛간에 대해, 농부들이 출구 헛간들에 최적으로 배치된다고 가정할 때, 베시가 그 헛간에서 모습을 드러내면 베시를 잡는 데 필요한 최소 농부 수를 구하도록 베시를 도와주자.
이 문제의 시간 제한은 기본값보다 약간 크다는 점에 유의하라: C/C++/Pascal은 4초, Java/Python은 8초이다.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)이 주어진다. 다음 \(N-1\)개의 줄에는 각각 \(1 \ldots N\) 범위의 정수 두 개가 주어지며, 두 헛간 사이의 터널을 나타낸다.
\(N\)개의 줄을 출력한다. \(i\)번째 줄에는 베시가 \(i\)번째 헛간에서 모습을 드러냈을 때 베시를 잡는 데 필요한 최소 농부 수를 출력한다.
atlarge.in · 출력을 쓸 파일 atlarge.out7
1 2
1 3
3 4
3 5
4 6
5 73
1
3
3
3
1
1riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > January > Platinum