P6277 [USACO20OPEN] Circus P

The $N$ cows in Farmer John's circus are preparing for an upcoming show. The entire show takes place on a tree with nodes numbered $1\ldots N$. An "initial state" of the show is defined by an integer $K$ ($1\leq K\leq N$), where cows $1\ldots K$ are placed on nodes of the tree, and no two cows are on the same node. During a show, the cows may "move" any number of times. In one "move", a cow can move from its current node to an unoccupied adjacent node. If one state can be reached from another through a sequence of moves, then we say these two initial states are equivalent. For each $1\leq K\leq N$, you need to help the cows determine how many equivalence classes of initial states there are. In other words, find the maximum number of initial states such that they are pairwise not equivalent. Since the number may be large, output the answer $\bmod \ 10^9+7$.

The first line contains an integer $N$. The next $N-1$ lines each contain two integers $a_i,b_i$, indicating that there is an edge in the tree connecting $a_i$ and $b_i$.

Output a total of $N$ lines. For each $1\leq i\leq N$, on line $i$ output the answer for $K=i$, taken $\bmod \ 10^9+7$.

#### Explanation of Sample $1$: For $K=1$ and $K=2$, any two states can be reached from each other. Now consider $K=3$. Let $c_i$ denote the position of cow $i$. Then the state $(c_1,c_2,c_3)=(1,2,3)$ is equivalent to the states $(1,2,5)$ and $(1,3,2)$, but it is not equivalent to the state $(2,1,3)$. ----- For $100\%$ of the testdata, it is guaranteed that $1 \le N \le 10^5$. There are $20$ test points. Among them, $1\sim 2$ are the samples, and the remaining points have the following properties: For test points $3 \sim 4$, $N \leq 8$. For test points $5 \sim 7$, $N \leq 16$. For test points $8 \sim 10$, $N \leq 100$, and the tree is a "star": at most one node has degree greater than $2$. For test points $11 \sim 15$, $N \leq 100$. For test points $16 \sim 20$, there are no special restrictions. ------ Problem setter: Dhruv Rohatgi Translated by ChatGPT 5