Задачи
Погоня за бабочкой
Погоня за бабочкой
Ясными летними днями Нюша любит ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она залетела в лабиринт и хотела скрыться в нем от Нюши.
Лабиринт состоит из $n$ комнат, пронумерованных от $1$ до $n$, некоторые из которых соединены между собой коридорами. Известно, что между любыми двумя комнатами существует единственный путь из коридоров. Иными словами, лабиринт представляет собой дерево, и количество коридоров равно $n - 1$.
Вход в лабиринт расположен в комнате с номером $1$. Будем называть листом любую комнату лабиринта, которая соединена коридором ровно с одной другой комнатой и не совпадает при этом с корнем. В каждом из листов располагается выход из лабиринта. Бабочка летит от входа по направлению к одному из листов. Она летит с постоянной скоростью и не разворачивается. Все коридоры имеют одинаковую длину, и за одну минуту бабочка пролетает один коридор, перемещаясь в соседнюю комнату.
Для поимки бабочки Нюша решила позвать несколько своих друзей. Исходно каждый из друзей может расположиться в любой из комнат, содержащих выход. В тот момент, когда бабочка начнет лететь от входа в лабиринт к одному из выходов, каждый из друзей может начать двигаться из своей комнаты по направлению ко входу. Друзья двигаются с такой же скоростью, что и бабочка. Если кто-то из друзей оказался в одной точке (в комнате или в середине одного из коридоров) с бабочкой, то бабочка считается пойманной. Если же бабочка долетит до вершины с выходом, не встретив никого из друзей по пути, она благополучно выпорхнет из лабиринта и улетит на свободу.
Помогите Нюше определить, какое минимальное число друзей понадобится для того, чтобы гарантированно поймать бабочку, вне зависимости от того, к какому выходу она полетит.
\InputFile
Первая строка содержит целое число $n\:(2 \le n \le 200000)$ --- количество комнат в лабиринте.
В следующих $n - 1$ строках содержатся описания коридоров, соединяющих комнаты. Каждая из этих строк содержит два целых числа $u$ и $v\:(1 \le u, v \le n, u ≠ v)$ --- номера комнат, которые соединяет коридор. Гарантируется, что структура коридоров представляет собой дерево.
\OutputFile
Выведите одно целое число --- минимальное количество друзей, необходимое для того, чтобы гарантированно поймать бабочку.
Входные данные #1
3 1 2 1 3
Выходные данные #1
2
Входные данные #2
4 1 2 2 3 2 4
Выходные данные #2
1