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

Автотуризм

Автотуризм

В Байтландии существуют \textbf{n }городов, соединённых \textbf{n - 1 }дорогами с двусторонним движением таким образом, что из каждого города можно проехать в любой другой по сети дорог. Длина каждой дороги равна \textbf{1 }километру. \includegraphics{https://static.e-olymp.com/content/25/254d8a9d98c9ee0ffb4ab8793ebc6098a6ebe751.jpg} Бензобак автомобиля позволяет проехать без заправки \textbf{m }километров. Требуется выбрать маршрут, позволяющий посетить наибольшее количество различных городов без дозаправки. При этом начинать и заканчивать маршрут можно в произвольных городах. \InputFile В первой строке заданы два целых числа \textbf{n }и \textbf{m }(\textbf{2 }≤ \textbf{n }≤ \textbf{500000}, \textbf{1 }≤ \textbf{m }≤ \textbf{200000000}) - количество городов в стране и количество километров, которое автомобиль может проехать без дозаправки. В последующих \textbf{n - 1 }строках описаны дороги. Каждая дорога задаётся двумя целыми числами \textbf{a }и \textbf{b }(\textbf{1 }≤ \textbf{a}, \textbf{b }≤ \textbf{n}) - номерами городов, которые она соединяет. Длина каждой дороги равна \textbf{1 }км. \OutputFile Выведите максимальное количество городов, которое можно посетить без дозаправки. \Note 5 городов можно посетить, например, по схеме 4 → 5 → 7 → 5 → 6 → 5 → 2 или по схеме 3 → 2 → 1 → 2 → 5 → 6 → 5.
Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB
Giriş verilənləri #1
7 7
2 4
1 2
5 6
6 7
2 3
6 1
Çıxış verilənləri #1
6
Mənbə 2012 Харьков, Зимняя школа, День Сергея Копеловича, Задача I