ЗАДАЧА C
Галчонок Хватайка
| Имя входного файла: | cherry.in |
| Имя выходного файла: | cherry.out |
| Ограничение по времени: | 1 секунда |
| Ограничение по памяти: | 64 Мб |
Возле дома дяди Федора росла огромная-преогромная вишня. И каждый год она давала огромный урожай. Вот и в этом году дядя Федор, кот Матроскин и Шарик наелись вишен до отвала. Но сезон закончился, дерево опустело, и на нем осталась всего одна вишенка.
Заметим, что, как и любое дерево, вишня представляет собой связный граф с N вершинами и N-1 ребром. Вершина под номером 1 является корнем дерева, а в вершине под номером K висит единственная вишенка.
Однажды галчонок Хватайка решил съесть эту одинокую вишенку. Но поскольку делать ему было нечего, то он решил немного развлечься. Изначально галчонок сел в корень (т.е. в вершину 1) дерева. Каждую минуту галчонок перелетает из текущей вершины в любую из соседних, т.е. таких, которые соединены с текущей вершиной веткой (т.е. ребром). Причем вершину, куда перелететь, он выбирает случайно, равновероятным образом. Когда галчонок оказывается в вершине, где растет вишенка, он ее съедает и с чувством выполненного долга летит отдыхать.
За более чем интересной игрой галчонка Хватайки внимательно наблюдал Шарик, прилегший отдохнуть под соседней яблоней. Дело в том, что Шарик недавно прочитал некоторые книги по теории вероятностей и теперь его очень интересовал вопрос: чему же равно математическое ожидание времени, которое пройдет до момента, когда галчонок все-таки съест вишенку. На этот интересный вопрос Шарик просит ответить вас.
Входные данные
Первая строка входного файла содержит два натуральных числа – количество вершин в дереве N (1 <= N <= 50) и номер вершины, где растет вишенка K (1 <= K <= N). Каждая из следующих N-1 строк описывает ветку дерева. Каждая такая строка содержит два натуральных числа X и Y (1 <= X < Y <= N), которые означают, что вершины X и Y соединяет ветка.
Выходные данные
В выходной файл выведите единственное вещественное число с четырьмя знаками после запятой – математическое ожидание времени (в минутах), которое потребуется галчонку, чтобы добраться до вишенки.
Пример
| cherry.in | cherry.out |
|---|---|
|
|