레이팅 미적용농부 존이 모든 밭에 풀을 심을 시기가 되었다. 농장 전체는 \(N\)개의 밭 (\(1 \leq N \leq 10^5\))으로 이루어져 있으며, 편의상 \(1 \ldots N\)번으로 번호가 매겨져 있고, 편리하게도 \(N-1\)개의 양방향 길로 연결되어 있어서 어떤 밭에서든 길들을 적절히 따라가면 다른 어떤 밭에도 도달할 수 있다.
농부 존은 밭마다 서로 다른 종류의 풀을 심을 수도 있지만, 사용하는 풀 종류가 많을수록 비용이 더 들기 때문에 전체적으로 사용하는 풀 종류의 수를 최소화하고 싶어한다.
안타깝게도 그의 소들은 농장의 풀 선택에 대해 꽤 까다로워졌다. 인접한 두 밭 (길로 직접 연결된 밭)이나, 심지어 거의 인접한 두 밭 (둘 다 길로 공통의 밭에 직접 연결된 밭)에 같은 종류의 풀이 심어져 있으면, 소들은 식사 선택지의 다양성이 부족하다고 불평할 것이다. 불만을 품은 소들이 그동안 얼마나 많은 말썽을 일으켜 왔는지를 생각하면, 농부 존에게 불평하는 소들은 결코 달갑지 않다.
농장 전체에 필요한 풀 종류의 최소 개수를 구하도록 농부 존을 도와주자.
출제자: Dhruv Rohatgi
출제자: Dhruv Rohatgi
입력의 첫째 줄에 \(N\)이 주어진다. 나머지 \(N-1\)개의 줄에는 각각 길 하나가 연결하는 두 밭이 주어진다.
농부 존에게 필요한 풀 종류의 최소 개수를 출력한다.
planting.in · 출력을 쓸 파일 planting.out4
1 2
4 3
2 33In this simple example, there are 4 fields all connected in a linear fashion. A
minimum of three grass types are needed. For example, Farmer John could plant
the fields with grass types A, B, and C as A - B - C - A.
riseoj 작성
출처 올림피아드 > USACO > 2018-2019 > January > Silver