P5197 [USACO19JAN] Grass Planting S

USACO January Contest Silver Problem 1.

It is the time of year when Farmer John plants grass in his fields. The entire farm consists of $N$ fields ($1 \leq N \leq 10^5$), conveniently labeled $1 \ldots N$, connected by $N-1$ bidirectional paths. From any field, it is possible to reach every other field by traveling along some paths. Farmer John could of course plant different types of grass in each field, but he wants to minimize the number of grass types used, because the more types he uses, the higher the cost he must pay. Unfortunately, his cows are very picky about the grass choices on the farm. If two adjacent fields (directly connected by a path) are planted with the same type of grass, or even if two nearly adjacent fields (both directly connected by a path to the same field) are planted with the same type of grass, then the cows will complain that their dining choices are not diverse enough. Farmer John can only complain about these cows, because he knows how much trouble they can cause when they are not satisfied. Please help Farmer John find the minimum number of grass types needed for the entire farm.

The first line contains $N$. The following $N-1$ lines each describe a path connecting two fields.

Output the minimum number of grass types Farmer John needs to use.

In this simple example, 4 fields are connected in a straight line. The minimum number of grass types needed is 3. For example, Farmer John can use grass $A,B,C$ to plant the fields as $A - B - C - A$. Translated by ChatGPT 5