Codeforces 917D. Stranger Trees

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 ≤ kn – 1, they’re going to investigate all labeled trees with n vertices that share exactly kedges 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 nvertices 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 = 109 + 7.

Input

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, unvu), endpoints of an edge. It is guaranteed that the given graph is a tree.

Output

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 1000 000 007 = 109 + 7.

Examples

题意简述

给出一棵树,对于 $k=0,1,2\cdots n-1$,分别求出有多少不同的树和给出的树恰好有 $k$ 条一样的边(包括给出的树)。答案需要取模。

分析

考虑在给出的树中固定 $k$ 条边,然后将其补充为一棵树的方案数,实际上就是这道题

可以看出,$k$ 不变时,最后的式子只跟各部分的大小有关系,所以我们可以想办法求出各部分大小乘积的和——可以利用树型 DP 解决,记状态 $f(i,j,k)$ 表示将 $i$ 节点所在的子树分成 $j$ 个部分,其中与 $i$ 相连的部分大小为 $k$,各部分(除了与 $k$ 相连的部分)的乘积之和,状态的转移就是简单的背包问题了。

做完 DP 就可以求出每一个 $k$ 补全的方案数了,但是有很多重复计算的部分,考虑将如何将这些剪掉。

我们设最终的答案为序列 $A$,而我们求出来的答案为序列 $B$。

对于一个 $k=i$ 的方案,从 $i$ 条边中任选 $j$ 条边的方案为 ${i \choose j}$,其中每一种方案都对应着一个固定了 $j$ 条边的加边方案,也就是说 $A_i$ 在 $B_j$ 中被加的次数为 ${i\choose j}$。

我们现在知道了从 $A$ 到 $B$ 的变换,只要求出它的逆变换就好了。实际上为了使变换更加直观,我们可以理解成 $B$ 是由 $A$ 依次做 $0$~$n-1$ 的后缀和、$1$~$n-1$ 的后缀和、……、$n-2$~$n-1$ 的后缀和得到。这样只要反过来做差分就可以得到结果了。

 

发表评论