3440：【2024年5月】6级算法等考第6题 学校数量
文件提交：无需freopen
内存限制：256 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
1
提交：0
解决：0
题目描述
## Description
给定包含n个节点的树形结构，每个节点表示一个居民社区，节点编号从1到n，1号节点为根节点，社区之间通过n-1条道路连接。当地政府打算在这些社区中建设一批学校和医院，要求如下：
1.每个社区只能选择建设一所学校或者医院，也可以选择什么都不建设；
2.除了表示叶子节点的社区外，其余节点要满足：以该节点作为根节点的子树中（包含节点自身），建设的学校的数量等于医院的数量。
请统计这n个社区中最多能建设多少所学校?
## Input Format
第一行包含一个整数n，表示居民社区的数量；
接下来n-1行，每行包含2个整数x，y，分别表示x号社区和y号社区之间有一条道路连接。
数据范围
测试点1~10：1≤n≤105，1≤x,y≤n。
## Output Format
一个整数，表示这n个社区最多能建设多少所学校。
```input1
5
1 2
1 3
3 4
3 5
```
```output1
2
```
```input2
6
1 2
2 3
3 4
4 5
4 6
```
```output2
1
```