#2034. 公交车与路灯修建

公交车与路灯修建

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

公交车是一名道路施工员,他要为城市Z修建路灯。

现在整个城市由N\red{N}个区域组成(1<N<=105)\red{(1<N<=10^5) }。为了方便起见,公交车把他们分别标号为1...N\red{1...N,}N1\red{N-1}条双向的小路连接,每块区域都可以经过一些小路到达其他的区域。公交车现在有若干种路 灯,公交车显然可以在每个区域中修建不同种类的路灯,但是为了省事,公交车想要使得使用的路灯 的种类数最小。

不幸的是,Z市市长pjh对路灯的修建有着非常苛刻的要求。如果两块相邻(有一条小路直接连接)的 区域中修建了同一种路灯,或者即使是两块接近相邻(均可由一条小路直接连向同一块区域)的区域 也修建了同一种路灯,那么市长pjh就会生气!

公交车必须要满足市长pjh的要求,但是公交车却不知道如何去做,现在你要做的就是帮帮可怜的公交 车,求出整个城市Z所需要的最少的路灯的种类数。

输入格式

输入的第一行包含N\red{N}

以下N1\red{N-1}行每行描述了一条小路连接的两块区域。

输出格式

输出公交车需要使用的最少的路灯的种类数

样例

输入样例

4
1 2
4 3
2 3

输出样例

3

集训班测试13

未参加
状态
已结束
规则
IOI
题目
3
开始于
2022-7-22 20:00
结束于
2022-7-23 20:00
持续时间
24 小时
主持人
参赛人数
13