徐老师的路灯修建
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师所在的城市最近要统一修建一批路灯，来装饰城市。
城市里一共有 $n$ 个路口，这 $n$ 个路口由 $n - 1$ 条道路相连。
而市长对于路灯的设置有一些自己的想法：
1. 如果两个相邻的路口用同一种路灯，会显得城市很单调
2. 如果两个间接相邻的路口用同一种路灯（两个能够直连到同一路口的路口被认为是间接相邻的路口），会显得城市很难看
现在市长非常头疼，他不知道到底要订几种不同的路灯，现在徐老师自告奋勇的希望帮市长解决问题
结果发现解决不了，于是只能求助于你，请你帮帮他。
输入格式
输入的第一行包含一个整数 $n$，表示路口数量。
接下来 $n - 1$ 行，每行包含两个整数 $x,y$ 表示 $x,y$ 两个路口是直接相连的
对于 $10\%$ 的数据满足：$n \leq 10$
对于 $50\%$ 的数据满足：$n \leq 50000$
对于 $100\%$ 的数据满足：$n \leq 10^5$
输出格式
输出最少需要订购几种不同的路灯
样例
4
1 2
4 3
2 332023暑假CSP-J模拟赛三
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-8-16 22:30
- 结束于
- 2023-8-26 22:30
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 46
