P5197 [USACO19JAN]Grass Planting

    • 97通过
    • 128提交
  • 题目提供者 泥土笨笨
  • 评测方式 云端评测
  • 标签 USACO 2019
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    USACO一月月赛银组第一题

    题目描述

    到了一年中Farmer John在他的草地里种草的时间了。整个农场由N块草地组成(1≤N≤10^5),方便起见编号为1…N,由N−1条双向的小路连接,每块草地都可以经过一些小路到达其他所有的草地。 Farmer John当然可以在每块草地里种不同种类的草,但是他想要使得使用的草的种类数最小,因为他用的草的种类数越多,他就需要负担更高的花费。

    不幸的是,他的奶牛们对选择农场上的草表现得十分苛刻。如果两块相邻(由一条小路直接相连)的草地种了同一种草,或者即使是两块接近相邻(均可由一条小路直接连向同一块草地)的草地,那么奶牛们就会抱怨她们进餐的选择不够多样。Farmer John能做的只能是抱怨这些奶牛,因为他知道她们不能被满足的时候会制造多大的麻烦。

    请帮助Farmer John求出他的整个农场所需要的最少的草的种类数。

    输入输出格式

    输入格式:

    输入的第一行包含N。以下N−1行每行描述了一条小路连接的两块草地。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    4
    1 2
    4 3
    2 3
    输出样例#1: 复制
    3

    说明

    在这个简单的例子中,4块草地以一条直线的形式相连。最少需要三种草。例如,Farmer John可以用草A,B和C将草地按A - B - C - A的方式播种。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。