题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Nadajniki

Bajtazar 成为字节镇下古老盐矿的新任主管。为了吸引更多游客，他决定在矿洞通道里安装无线网络。

盐矿有 $n$ 个腔室，通过 $n-1$ 条通道相连，任何两个腔室都能通过通道到达。Bajtazar 计划在腔室中放置 Wi-Fi 发射器，确保每条通道都有网络覆盖。要让连接腔室 $a$ 和 $b$ 的通道有网络，需满足以下至少一个条件：

• 腔室 $a$ 或 $b$ 中有发射器；
• 从腔室 $a$ 或 $b$ 出发，最多经过一条通道可达的腔室集合中，至少有两个发射器。

Bajtazar 想知道，至少需要放置多少发射器才能覆盖所有通道。每间腔室可放置任意多个发射器。

输入格式

输入第一行是一个正整数 $n$，表示盐矿的腔室数量，腔室编号从 $1$ 到 $n$。

接下来的 $n-1$ 行描述通道，每行两个整数 $a$ 和 $b$ $(1 \leq a, b \leq n, a \neq b)$，表示 $a$ 号和 $b$ 号腔室间有一条通道。

输出格式

输出一行一个整数，表示 Bajtazar 所需的最少发射器数量。

7
1 2
2 3
2 4
4 5
5 6
6 7

2

第一个样例中，在 $2$ 号和 $6$ 号腔室各放一个发射器即可；第二个样例中，在 $3$ 号腔室放两个发射器即可。

7
1 2
2 3
4 3
5 4
6 3
7 6

2

附加样例

1. $n=16$，腔室 $i$ 与 $\lfloor i / 2 \rfloor$ $(2 \leq i \leq n)$ 相连；
2. $n=303$，$2$ 号腔室连 $1$ 号和 $3$ 号，$1$、$2$、$3$ 号各连 $100$ 个其他腔室，最优解在 $2$ 号腔室放两个发射器；
3. $n=200000$，腔室 $i$ 与 $i+1$ $(1 \leq i \leq n-1)$ 相连。

数据范围与提示

详细子任务附加限制及分值如下表所示。