苏老师的路灯修建
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
说明
苏老师所在的城市最近要统一修建一批路灯，来装饰城市。
城市里一共有 $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普及组模拟赛2
- Status
- Done
- Rule
- OI
- Problem
- 4
- Start at
- 2023-10-2 8:30
- End at
- 2023-10-2 18:30
- Duration
- 3.5 hour(s)
- Host
-
sulaoshi
- Partic.
- 2