#PU1046. USACO 2020 US Open Contest, Platinum — Problem 3. Circus

    ID: 1611 传统题 文件IO:circus 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:open20来源:usaco.orgscoring:equal_test_cases树形DP数学

USACO 2020 US Open Contest, Platinum — Problem 3. Circus

USACO 2020 US Open Contest, Platinum — Problem 3. Circus

题目描述

The NN cows of Farmer John's Circus (1≤N≤1051 \leq N \leq 10^5) are preparing their upcoming acts. The acts all take place on a tree with vertices labeled 1…N1\ldots N. The "starting state" of an act is defined by a number 1≤K≤N1 \leq K \leq N and an assignment of cows 1…K1\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≤K≤N1 \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,

输入格式

Line 11 contains NN. Lines 2≤i≤N2\le i\le N each contain two integers aia_i and bib_i denoting an edge between aia_i and bib_i in the tree.

输出格式

For each 1≤i≤N,1\le i\le N, the ii-th line of output should contain the answer for K=iK=i modulo 109+710^9+7.

数据范围

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

样例

样例 1

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).$

样例 2

8
1 3
2 3
3 4
4 5
5 6
6 7
6 8
1
1
1
6
30
180
5040
40320