Stranger Trees

题意翻译

给定一棵有n个节点的无权无向树 求对于这n个点，以及每个k=0,1,2...n-1，有多少棵由这n个点之间的边构造成的树，与给定的树恰好有k条边重复 答案 MOD 1e9+7 输出 e.g. n=3, edge ={(1,2),(1,3)} ， ans[0]={}，ans[1]={ tree{(2,3),(1,3),tree{(2,3),(1,2)} },ans[2]={ tree{(1,2),(1,3)} } （即为第一个样例） Translated by KamijuIndex

题目描述

Will shares a psychic connection with the Upside Down Monster, so everything the monster knows, Will knows. Suddenly, he started drawing, page after page, non-stop. Joyce, his mom, and Chief Hopper put the drawings together, and they realized, it's a labeled tree! A tree is a connected acyclic graph. Will's tree has $ n $ vertices. Joyce and Hopper don't know what that means, so they're investigating this tree and similar trees. For each $ k $ such that $ 0<=k<=n-1 $ , they're going to investigate all labeled trees with $ n $ vertices that share exactly $ k $ edges with Will's tree. Two labeled trees are different if and only if there's a pair of vertices $ (v,u) $ such that there's an edge between $ v $ and $ u $ in one tree and not in the other one. Hopper and Joyce want to know how much work they have to do, so they asked you to tell them the number of labeled trees with $ n $ vertices that share exactly $ k $ edges with Will's tree, for each $ k $ . The answer could be very large, so they only asked you to tell them the answers modulo $ 1000000007=10^{9}+7 $ .

输入输出格式

输入格式

The first line of input contains a single integer $ n $ ( $ 2<=n<=100 $ ) — the size of the tree. The next $ n-1 $ lines contain the edges of Will's tree. Each line contains two integers $ v $ and $ u $ ( $ 1<=v,u<=n $ , $ v≠u $ ), endpoints of an edge. It is guaranteed that the given graph is a tree.

输出格式

Print $ n $ integers in one line. $ i $ -th integer should be the number of the number of labeled trees with $ n $ vertices that share exactly $ i-1 $ edges with Will's tree, modulo $ 1000000007=10^{9}+7 $ .

输入输出样例

输入样例 #1

3
1 2
1 3

输出样例 #1

0 2 1 

输入样例 #2

4
1 2
2 3
3 4

输出样例 #2

1 7 7 1 

输入样例 #3

4
1 2
1 3
1 4

输出样例 #3

0 9 6 1