eolymp
bolt
Try our new interface for solving problems
Məsələlər

Заражение

Заражение

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Фермер Джон и его коллеги-фермеры работают без перерыва, чтобы контролировать распространение страшной болезни крупного рогатого скота COWVID-19 на своих фермах.

Вместе они наблюдают за n фермами, пронумерованных от 1 до n. Фермы соединены n − 1 дорогой, так что к любой ферме можно добраться от фермы 1 по некоторой последовательности дорог.

К сожалению, корова на ферме 1 только что дала положительный результат на COWVID-19. Ни одна из других коров на этой или других фермах еще не болеет. Однако, зная заразную природу болезни, фермер Джон предвидит одно из следующих неблагоприятных событий каждый последующий день:

  • На одной ферме событие "суперразброс" приводит к удвоению количества коров с COWVID-19;

  • Одна корова с COWVID-19 движется по дороге от одной фермы к соседней.

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

Giriş verilənləri

Первая строка содержит единственное целое число n~(1 \le n \le 10^5). Каждая из следующих n - 1 строк содержит два целых числа a и b, описывающих дорогу между фермами a и b. Оба значения a и b находятся в диапазоне 1 ... n.

Çıxış verilənləri

Выведите минимальное количество дней до того, как вспышка болезни достигнет каждой фермы.

Nümunə

Одна из возможных последовательностей событий, соответствующая этому примеру, следующая: количество больных коров на ферме 1 удваивается, затем снова удваивается, так что через два дня на ферме 1 оказывается 4. В каждый из следующих 3 дней больная корова идет с фермы 1 на каждую из ферм 2, 3 и 4 соответственно. Через 5 дней на каждой ферме будет как минимум 1 больная корова.

Giriş verilənləri #1
4
1 2
1 3
1 4
Çıxış verilənləri #1
5
Mənbə 2020 USACO Декабрь, Серебро