P10632 Normal

One day, WJMZBMR learned a magical algorithm: centroid decomposition on a tree. The core idea of this algorithm is as follows: ```cpp time = 0 Solve(Tree a) { time += a.size; if (a.size == 1) return; else { select x in a; delete a[x]; } } ``` ``` Time cost = 0 Solve(tree a) Time cost += size of a If there is only 1 node in a Exit Otherwise Choose a node x in a Delete node x from a ``` Then $a$ becomes several smaller trees, and `Solve` is called recursively on each subtree. We notice that the time complexity of this algorithm is closely related to the chosen node $x$. If $x$ is the centroid of the tree, then the time complexity is $O(n \log n)$. WJMZBMR decides to choose a node in $a$ uniformly at random as $x$. Sevenkplus tells him that the worst-case complexity of doing this is $O(n^2)$, but WJMZBMR does not believe it. So Sevenkplus spent a few minutes writing a program to prove it. You can try it too. Now you are given a tree. Can you tell WJMZBMR the expected time cost of his algorithm (using the definition in the given `Solve` function as the standard)?

The first line contains an integer $n$, the size of the tree. The next $n-1$ lines each contain two integers $a, b$, meaning there is an edge between $a$ and $b$. The nodes of the tree are numbered starting from $0$.

Output one line with a floating-point number, the answer rounded to $4$ digits after the decimal point.

For all testdata, it is guaranteed that $1\leq n\leq 30000$. Translated by ChatGPT 5