P6925: 种植计划
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
到了一年中Farmer John
在他的草地里种草的时间了。整个农场由N
块草地组成（1≤N≤10
^5
），方便起见编号为1…N
，由N−1
条双向的小路连接，每块草地都可以经过一些小路到达其他所有的草地。
Farmer John
当然可以在每块草地里种不同种类的草，但是他想要使得使用的草的种类数最小，因为他用的草的种类数越多，他就需要负担更高的花费。
不幸的是，他的奶牛们对选择农场上的草表现得十分苛刻。如果两块相邻（由一条小路直接相连）的草地种了同一种草，或者即使是两块接近相邻（均可由一条小路直接连向同一块草地）的草地，那么奶牛们就会抱怨她们进餐的选择不够多样。Farmer John
能做的只能是抱怨这些奶牛，因为他知道她们不能被满足的时候会制造多大的麻烦。
请帮助Farmer John
求出他的整个农场所需要的最少的草的种类数。
【
输入格式】
（文件名：planting.in
）：
输入的第一行包含N
。以下N−1行每行描述了一条小路连接的两块草地。
【
输出格式】
（文件名：planting.out
）：
输出Farmer John
需要使用的最少的草的种类数。
【
输入样例】
：
4
1 2
4 3
2 3
【
输出样例】
：
3
【样例说明】
在这个简单的例子中，4
块草地以一条直线的形式相连。最少需要三种草。例如，Farmer John可以用草A，B和C将草地按A - B - C - A的方式播种。