32664번 - Cascade Centrality 스페셜 저지다국어

문제

Given an undirected graph $G=(V,E),ドル the cascade centrality of node $i$ in $V$ is defined to be: $1ドル + \sum_{j \in V \setminus \{i\}} \sum_{P \in P_{ij}} \frac{1}{\chi_P},$$ where $P_{ij}$ is the set of all simple paths from node $i$ to node $j,ドル and the degree sequence product $\chi_P$ of a path is the product of the degrees of all nodes along the path, including the ending node but excluding the starting node.

In this problem, $G$ is a tree, so that $P_{ij}$ always contains exactly one path. Find the mean of the cascade centralities of the nodes in $G$.

입력

The first line of input consists of an integer $N$ $(1 \leq N \leq 100),ドル the number of nodes in the tree.

The remaining $N-1$ lines each contains two space-separated integers $u_i$ and $v_i$ $(1 \leq u_i, v_i \leq N),ドル denoting an undirected edge from node $u_i$ to node $v_i$. No edge connects a node to itself, and there is at most one edge between any pair of nodes.

The given graph is a tree: it is connected and does not contain a cycle.

출력

Print the mean of the cascade centralities of the nodes in the input graph. Your solution will be judged correct if it differs from the judge solution by at most 10ドル^{-6}$ relative or absolute error.

제한

힌트