Random Tree Generation
골드 II의견: 0
Suppose the function \(\text{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 \le N \le 2\cdot10^5\)) 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 \(\text{randint}(1, i-1)\).
- Choose a permutation \(p_1,p_2,\dots,p_N\) of \(\{1, 2, \ldots, N\}\) uniformly at random. Relabel every vertex \(v\) as \(p_v\).
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 \(10^9+7\)?
Problem credits: Benjamin Qi
SCORING
- Input 2-3: \(N\le 8\)
- Inputs 4-9: \(N\le 2000\)
- Inputs 10-21: No additional constraints.
Problem credits: Benjamin Qi
The input consists of \(T\) (\(1\le T\le 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\le u, v\le 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\cdot 10^5\).
For each test, output the probability modulo \(10^9+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 \(10^9+7\)).
4
2
2 1
3
1 2
2 3
4
1 2
2 3
2 4
4
1 2
2 3
3 41
333333336
83333334
55555556The 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\equiv 333333336\pmod{10^9+7}\).
riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Gold
평가 및 의견
Random Tree Generation
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Random Tree Generation