The \(N\) cows of Farmer John's Circus (\(1 \leq N \leq 10^5\)) are preparing their
upcoming acts. The acts all take place on a tree with vertices labeled
\(1\ldots N\). The "starting state" of an act is defined by a number
\(1 \leq K \leq N\) and an assignment of cows \(1\dots K\) to the vertices of the
tree, so that no two cows are located at the same vertex.

In an act, the cows make an arbitrarily large number of "moves." In a move, a
single cow moves from her current vertex to an unoccupied adjacent vertex. Two
starting states are said to be equivalent if one may be reached from the other
by some sequence of moves.

For each \(1 \leq K \leq N\), help the cows determine the number of equivalence
classes of starting states: that is, the maximum number of starting states they
can pick such that no two are equivalent. Since these numbers may be very large,
output their remainders modulo \(10^9 + 7\).

Problem credits: Dhruv Rohatgi

SCORING

• Test cases 3-4 satisfy \(N\le 8.\)
• Test cases 5-7 satisfy \(N\le 16.\)
• Test cases 8-10 satisfy \(N\le 100\) and the tree forms a "star;" at most one vertex has degree greater than two.
• Test cases 11-15 satisfy \(N\le 100\).
• Test cases 16-20 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

Line \(1\) contains \(N\).

Lines \(2\le i\le N\) each contain two integers \(a_i\) and \(b_i\) denoting an edge
between \(a_i\) and \(b_i\) in the tree.

For each \(1\le i\le N,\) the \(i\)-th line of output should contain the answer for
\(K=i\) modulo \(10^9+7\).

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Platinum