1796. 蝴蝶
时间限制：1000 MS 内存限制：128 MB
题目描述
## 题目描述 小火龙家的大房子进去了一只美丽的蝴蝶，小火龙和一些小朋友们来捉它。大房子里有依次编号为 $1 \sim n$ 的 $n$个房间和 $n-1$条走廊，任意一个房间都有至少有一条走廊连接。这 $n$ 个房间和 $n-1$ 条走廊就可以看做成一棵树，房间就是结点，$1$ 号房间我们认为是根节点。 蝴蝶从 $1$ 号房间飞进来，想从出口出去，而只有叶子结点有出口。蝴蝶可以用一分钟飞过一条走廊并进入一个房间，小朋友的移动速度和蝴蝶一样。 一开始，小朋友可以在叶子结点的房间里呆着准备抓蝴蝶，当小朋友和蝴蝶相遇时，蝴蝶就被捉住了。 给出大房子的构造，请你计算包括小火龙在内至少需要几个小朋友才能将这只美丽的蝴蝶抓住吗？ ## 输入格式 第一行输入一个正整数 $n$ ，代表房间总数。 接下来输入 $n-1$ 行，每行输入以空格分隔的两个正整数 $u,v$ ，代表由走廊连接的两个房间的编号。 保证构造的是一棵树。 $2 \le n \le 2 \times 10^5$ $1\le u, v\le n$ $u\neq$ ## 输出格式 输出至少需要几个小朋友才能将蝴蝶抓住 ## 数据范围 ... ## 输入 ```in1 3 1 2 1 3 ``` ## 输出 ```out1 2 ``` ```in2 4 1 2 2 3 2 4 ``` ```out2 1 ``` ```in3 ... ``` ```out3 ... ``` ## 提示