레이팅 미적용마침내 궁지에 몰린 베시는 외딴 농장에 숨어들었다. 이 농장은 \(N\)개의 헛간 (\(2 \leq N \leq 10^5\))과 헛간 사이를 잇는 \(N-1\)개의 양방향 터널로 이루어져 있어서, 모든 헛간 쌍 사이에 유일한 경로가 존재한다. 터널이 하나뿐인 헛간은 모두 출구이다. 아침이 오면 베시는 어떤 헛간에서 지상으로 나와 출구에 도달하려고 시도할 것이다.
하지만 베시가 지상에 나오는 순간, 경찰은 그녀의 위치를 정확히 파악할 수 있다. 그러면 몇몇 농부들이 여러 출구 헛간에서 출발하여 베시를 잡으려고 시도한다. 농부들은 베시와 같은 속도로 이동한다 (즉, 각 시간 단계마다 각 농부는 한 헛간에서 인접한 헛간으로 이동할 수 있다). 농부들은 항상 베시의 위치를 알고 있고, 베시도 항상 농부들의 위치를 알고 있다. 어느 순간이든 농부가 베시와 같은 헛간에 있거나 베시와 같은 터널을 지나가고 있으면 농부들이 베시를 잡는다. 반대로, 어떤 농부에게도 잡히기 전에 베시가 출구 헛간에 도달하면 베시가 탈출한다.
베시는 자신의 성공 가능성을 확신하지 못하는데, 이는 경찰이 투입할 수 있는 농부의 수에 달려 있다. 베시가 헛간 \(K\)에서 지상으로 나온다고 할 때, 농부들이 출구 헛간들에 최적으로 배치된다는 가정 아래 베시를 잡는 데 필요한 최소 농부 수를 구해 베시를 도와주자.
Problem credits: Dhruv Rohatgi
Problem credits: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)과 \(K\)가 주어진다. 다음 \(N-1\)개의 줄에 각각 \(1 \ldots N\) 범위의 두 정수가 주어지며, 두 헛간 사이의 터널을 의미한다.
베시를 확실히 잡는 데 필요한 최소 농부 수를 출력한다.
atlarge.in · 출력을 쓸 파일 atlarge.out7 1
1 2
1 3
3 4
3 5
4 6
5 73