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.