| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 32 | 12 | 10 | 35.714% |
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$.
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$.
5 1 2 2 3 3 4 3 5
1 1 3 24 120
For $K=1$ and $K=2,$ any two states can be transformed into one another.
Now consider $K=3,ドル and let $c_i$ denote the location of cow $i$. The state $(c_1,c_2,c_3)=(1,2,3)$ is equivalent to the states $(1,2,5)$ and $(1,3,2).$ However, it is not equivalent to the state $(2,1,3).$
8 1 3 2 3 3 4 4 5 5 6 6 7 6 8
1 1 1 6 30 180 5040 40320