28628번 - Погоня за бабочкой 다국어

Ясными летними днями Нюша любит ловить бабочек на свежем воздухе. Сегодня ей попалась хитрая бабочка: она залетела в лабиринт и хотела скрыться в нем от Нюши.

Лабиринт состоит из $n$ комнат, пронумерованных от $1$ до $n$, некоторые из которых соединены между собой коридорами. Известно, что между любыми двумя комнатами существует единственный путь из коридоров. Иными словами, лабиринт представляет собой дерево, и количество коридоров равно $n - 1$.

Вход в лабиринт расположен в комнате с номером $1$. Будем называть листом любую комнату лабиринта, которая соединена коридором ровно с одной другой комнатой и не совпадает при этом с корнем. В каждом из листов располагается выход из лабиринта. Бабочка летит от входа по направлению к одному из листов. Она летит с постоянной скоростью и не разворачивается. Все коридоры имеют одинаковую длину, и за одну минуту бабочка пролетает один коридор, перемещаясь в соседнюю комнату.

Для поимки бабочки, Нюша решила позвать несколько своих друзей. Исходно каждый из друзей может расположиться в любой из комнат, содержащих выход. В тот момент, когда бабочка начнет лететь от входа в лабиринт к одному из выходов, каждый из друзей может начать двигаться из своей комнаты по направлению ко входу. Друзья двигаются с такой же скоростью, что и бабочка. Если кто-то из друзей оказался в одной точке (в комнате или в середине одного из коридоров) с бабочкой, то бабочка считается пойманной. Если же бабочка долетит до вершины с выходом, не встретив никого из друзей по пути, она благополучно выпорхнет из лабиринта и улетит на свободу.

Помогите Нюше определить, какое минимальное число друзей понадобится для того, чтобы гарантированно поймать бабочку, вне зависимости от того, к какому выходу она полетит.

Первая строка входных данных содержит целое число $n$ --- количество комнат в лабиринте ($2 \le n \le 200\,000$).

В следующих $n - 1$ строках содержатся описания коридоров, соединяющих комнаты. Каждая из этих строк содержит два целых числа $u$ и $v$ --- номера комнат, которые соединяет коридор ($1 \le u, v \le n$; $u \neq v$). Гарантируется, что структура коридоров представляет собой дерево.

Выведите одно целое число --- минимальное количество друзей, необходимое для того, чтобы гарантированно поймать бабочку.