Grass Planting

题目描述

又到了一年中 Farmer John 要在所有田地里播种牧草的时候了。 整个农场由 $N$ 块田地组成（$1 \leq N \leq 10^5$），方便起见编号为 $1 \ldots N$，并通过 $N-1$ 条双向小路连接，使得任意一块田地都可以通过一些小路到达任何其他田地。

Farmer John 可以在每块田地里种植不同种类的牧草，但他希望尽量减少使用的牧草种类总数，因为使用的种类越多，花费就越高。

不幸的是，他的奶牛对农场里的牧草选择变得很挑剔。如果相同的牧草种类被种在两块相邻的田地上（由一条小路直接连接），甚至是两块“近邻”的田地上（它们都通过小路直接连接到同一块公共田地），奶牛就会抱怨餐食选择缺乏多样性。考虑到奶牛不满时会制造多少麻烦，Farmer John 最不需要的就是抱怨的奶牛。

请帮助 Farmer John 确定整个农场所需的最少牧草种类数。

输入格式

第一行输入 $N$。接下来的 $N-1$ 行每行描述一条小路，给出它连接的两块田地编号。

输出格式

输出 Farmer John 需要使用的最少牧草种类数。

4
1 2
4 3
2 3

3

提示

在这个简单例子中，有 4 块田地以线性方式连接。 至少需要三种牧草。例如，Farmer John 可以将田地分别种为 A、B、C 三种牧草，排列为 A - B - C - A。 题目贡献者：Dhruv Rohatgi

标签: USACO|2019|Silver

来源

USACO|2019|Silver