Рассмотрим дерево \(T\) (связный неориентированный граф без циклов) с \(n\) вершинами, пронумерованными целыми числами от \(1\) до \(n\). Запустим следующий процесс на \(T\): пока в \(T\) более одной вершины, делать следующее:
Когда процесс завершится, \(T\) будет состоять из одной вершины, с номером из \(1, \ldots, n\). Найдите для каждого числа вероятность, что это число окажется номером финальной вершины.
В первой строке входного файла записано целое число \(n\) (\(1 \leq n \leq 50\)).
Следующие \(n - 1\) строк описывают ребра дерева. Каждая из этих строк содержит два целых числа \(u_i, v_i\) — номера вершин, соединенных соответствующим ребром (\(1 \leq u_i, v_i \leq n\), \(u_i \neq v_i\)). Гарантируется, что данный граф является деревом.
Выведите \(n\) вещественных чисел — описанные вероятности для номеров \(1, \ldots, n\), соответственно. Все числа должны быть правильными с точностью до абсолютной или относительной погрешности \(10^{-6}\).
В первом примере, получившаяся вершина будет иметь номер 1 тогда и только тогда, когда для всех ребер вершина 1 выживет, соответственно вероятность равна \(1/2^3 = 1/8\). Все остальные числа имеют равную вероятность из-за симметрии, таким образом, каждое из них имеет вероятность \((1 - 1/8) / 3 = 7/24\).
4 1 2 1 3 1 4
0.1250000000 0.2916666667 0.2916666667 0.2916666667
7 1 2 1 3 2 4 2 5 3 6 3 7
0.0850694444 0.0664062500 0.0664062500 0.1955295139 0.1955295139 0.1955295139 0.1955295139
2000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач