Random Tree Generation
Suppose the function randint(l,r) returns an integer independently and uniformly at random from the range [l,r].
Bessie generates a random labeled tree on N vertices (2≤N≤2⋅105) using the following two-step process:
- Start with vertices labeled 1 through N. For each i from 2 to N, add an edge between vertex i and randint(1,i−1).
- Choose a permutation p1,p2,…,pN of {1,2,…,N} uniformly at random. Relabel every vertex v as pv.
Now, Farmer John is looking at the edge set of the final tree and wants to know the probability that the two-step process above produces a tree with exactly this edge set. Can you determine this probability modulo 109+7?
The probabilities are 1, 1/3, 1/12, 1/18.
First test: There is only one tree on N=2 vertices, so the probability of generating it is just 1.
Second test: there are three trees on N=3 vertices, and each of them is equally likely to have been generated by the process above. And 1/3≡333333336(mod109+7).
SCORING:
- Input 2-3: N≤8
- Inputs 4-9: N≤2000
- Inputs 10-21: No additional constraints.
Problem credits: Benjamin Qi
Source: USA Computing Olympiad.
Input Format
The input consists of T (1≤T≤10) independent inputs. Each input is specified as follows:
The first line contains N.
The next N−1 lines contain the edges of the tree specified by two space-separated integers u and v (1≤u,v≤N). It is guaranteed that these edges induce a tree.
It is guaranteed that the sum of N across all tests does not exceed 5⋅105.
Output Format
For each test, output the probability modulo 109+7 on a new line (note that the output probability is a ratio of integers, so you will want to print the result of this division when working modulo 109+7).