| Технокубок 2019 - Отборочный Раунд 4 |
|---|
| Закончено |
Вам дано дерево (неориентированный связный граф без циклов) и целое число $$$s$$$.
Ваня хочет как-то поставить веса на всех ребрах дерева, так что все веса неотрицательные вещественные числа, которые в сумме дают $$$s$$$. При этом он хочет, чтобы диаметр получившегося после расстановки весов дерева был как можно меньше. Диаметром будем называть максимальную сумму весов ребер, лежащих на пути между какими-то двумя вершинами дерева.
Найдите минимальный возможный диаметр, который мог у него получиться.
В первой строке даны два целых числа $$$n$$$ и $$$s$$$ ($$$2 \leq n \leq 10^5$$$, $$$1 \leq s \leq 10^9$$$) — количество вершин в дереве и сумма весов ребер.
В каждой из следующих $$$n−1$$$ строк через пробел записаны по два целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$) — номера вершин, соединенных ребром.
Гарантируется, что заданные ребра задают дерево.
Выведите минимальный диаметр дерева, который мог получиться при какой-то расстановке неотрицательных весов на ребра этого дерева, которые в сумме дают $$$s$$$.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не будет превосходить $$$10^{-6}$$$.
А именно: пусть ваш ответ равен $$$a$$$, а ответ жюри $$$b$$$. Ваш ответ будет засчитан, если $$$\frac {|a-b|} {max(1, b)} \leq 10^{-6}$$$.
4 3 1 2 1 3 1 4
2.000000000000000000
6 1 2 1 2 3 2 5 5 4 5 6
0.500000000000000000
5 5 1 2 2 3 3 4 3 5
3.333333333333333333
В первом примере необходимо расставить веса так:
Легко видеть, что диаметр такого дерева будет равен $$$2$$$. Можно доказать, что это минимально возможный диаметр, который можно получить, как-то расставив веса.
Вo втором примере необходимо расставить веса так:
