Problem D
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$.
Input
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.
Output
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.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
1.000000 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 2 |
2.000000 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 3 3 2 |
2.333333 |
