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$ 个房子，编号依次为 $1$ 到 $n$，这些房子通过 $n-1$ 条无向道路连通在一起，形成了一棵树的结构。

Bytesear 要在比特镇实施 Wifi 搭建计划，他要让 Wifi 覆盖到比特镇的每一条道路。

Bytesear 可以安置无限多个 Wifi 发射器，但是只能安置在树上的节点上，一个房子可以安置多个 Wifi 发射器。

对于一条道路 $(a,b)$，如果它满足以下两个条件之中的至少一个，那么这条边将被 Wifi 覆盖：

• $a$ 点放置了 Wifi 发射器或者 $b$ 点放置了 Wifi 发射器。
• 与 $a$ 点或 $b$ 点直接相邻的点中，至少放置了两个 Wifi 发射器。

请帮助 Bytesear 规划一个最优的放置方案，使得 Wifi 覆盖到比特镇的每一条道路，且放置的 Wifi 发射器总数尽可能少。

输入格式

第一行包含一个正整数 $n$，表示房子的总数。

接下来 $n-1$ 行，每行两个正整数 $a,b$，表示 $a$ 点和 $b$ 点之间有一条边。

输出格式

输出一行一个整数，即最少的 Wifi 发射器总数。

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

2

提示

对于 $100\%$ 的数据，$2\le n\le2 \times 10^5$，$1\le a,b\le n$。

样例解释：

在 $3$ 号点放置两个 Wifi 发射器。