最小点覆盖树

提高-⏱ 1000ms💾 256MB#P7015

题目描述

给一棵 $n$ 个点的树,选最少的点使得每条边至少有一个端点被选中。输出最少点数。

输入格式

第一行整数 $n$;接下来 $n-1$ 行每行一条边。

输出格式

一行一个整数。

数据范围

$$1 \le n \le 10^5$$

样例输入 #1
1
样例输出 #1
0
样例输入 #2
2
1 2
样例输出 #2
1