Probability of Isomorphic Increasing Tree

Consider an undirected tree T with n nodes. The tree is given as an unlabeled (free) tree. In Small P's random process, starting with node 1, for every node i from 2 to n, a parent is chosen uniformly at random from the set of nodes {1, 2, …, i-1} and an edge is inserted between them. Note that the resulting tree is a labeled increasing tree having vertex 1 as the root (because it never chooses a parent) and the labels appear in the order of insertion.

We say that two trees are isomorphic if one can be re‐labeled to obtain the other. In other words, you need to compute the probability that a tree generated by Small P's process is isomorphic to the given free tree T.

A key observation is that every outcome of the process is an increasing tree on {1, 2, …, n} with 1 as the root. There are exactly (n-1)! outcomes (since for each i from 2 to n, there are (i-1) choices, so the product is (n-1)!).

For a given free tree T, a valid isomorphic outcome is one that, under some isomorphism, maps the generated labeled tree (with vertex 1 as the designated root) to T. Equivalently, if we choose a vertex r of T to be the image of vertex 1, then the remaining labels must form a heap‐ordering on T when T is rooted at r (i.e. the label assigned to each vertex is less than the labels on its descendants). By the well–known tree hook length formula, the number of increasing labelings of a rooted tree (with n nodes and root r, automatically having the smallest label at r) is

[ L(T, r) = \frac{n!}{\prod_{v \in T} h_v}, ]

where for each vertex v, (h_v) denotes the size of the subtree of v in T when rooted at r. However, note that even if the free tree T has several increasing labelings (when rooted at different vertices), the process only yields one fixed labeled tree (with vertex 1 fixed). Hence the probability that the generated labeled tree is isomorphic to T is given by

[ P(T) = \frac{\displaystyle \sum_{r \in V(T)} \frac{1}{\prod_{v \in T_r} h_v}}{(n-1)!} \times (n-1)! = \sum_{r \in V(T)} \frac{1}{\prod_{v \in T_r} h_v}. ]

In other words, for every possible choice of r in T (which would be the image of the fixed vertex 1), compute the product of the subtree sizes (the hook lengths) when T is rooted at r, and take the sum of their reciprocals. This sum is the desired probability.

Your task is: Given an undirected tree T with n nodes (the first line contains n; the next n-1 lines each contain two integers representing an edge), compute and print the probability that a tree generated by Small P’s process is isomorphic to T. Print the answer as a floating–point number with 6 decimal places.

inputFormat

The first line contains an integer n (the number of nodes). The following n-1 lines each contain two space-separated integers u and v (1 ≤ u,v ≤ n), representing an edge of the tree.

outputFormat

Output the probability that a tree generated by the process is isomorphic to the given tree, as a floating–point number rounded to 6 decimal places.

sample

2
1 2

1.000000