Рассмотрим дерево \(T\) (связный неориентированный граф без циклов) с \(n\) вершинами, пронумерованными целыми числами от \(1\) до \(n\). Запустим следующий процесс на \(T\): пока в \(T\) более одной вершины, делать следующее:
- равновероятно выбрать случайное ребро \(T\);
- стянуть выбранное ребро: если ребро соединяло вершины \(v\) и \(u\), удалить и \(v\), и \(u\), и создать новую вершину, смежную со всеми вершинами, которые до этого были смежны или с \(v\), или с \(u\). Новая вершина равновероятно получает номер или \(v\), или \(u\).
Когда процесс завершится, \(T\) будет состоять из одной вершины, с номером из \(1, \ldots, n\). Найдите для каждого числа вероятность, что это число окажется номером финальной вершины.
Выходные данные
Выведите \(n\) вещественных чисел — описанные вероятности для номеров \(1, \ldots, n\), соответственно. Все числа должны быть правильными с точностью до абсолютной или относительной погрешности \(10^{-6}\).
Примечание
В первом примере, получившаяся вершина будет иметь номер 1 тогда и только тогда, когда для всех ребер вершина 1 выживет, соответственно вероятность равна \(1/2^3 = 1/8\). Все остальные числа имеют равную вероятность из-за симметрии, таким образом, каждое из них имеет вероятность \((1 - 1/8) / 3 = 7/24\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1 2
1 3
1 4
|
0.1250000000
0.2916666667
0.2916666667
0.2916666667
|
|
2
|
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
|