Stranger Trees
Contest: Codeforces Round 459 (Div. 1)
Difficulty rating: 2600
Tags: dp, math, matrices, 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 ≤ 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 = 109 + 7.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Example input:
3
1 2
1 3

Example output:
0 2 1

Example input:
4
1 2
2 3
3 4

Example output:
1 7 7 1

Editorial:
Solution #1:
First, for every K such that 0 ≤ K ≤ N - 1 we are going to find for every K edges in the original tree we are going to find the number of labeled trees having these K edges, then we will add them all to res[K].
But Mr. Author aren't we going to count some tree that has exactly E (where E > K) common edges with the original tree in res[K]? Yes, that's true. But we only count it $${ \binom { E } { K } }$$ times! So, after computing the res array we are going to iterate from N - 1 to 0 assuming that the res is correct for all J > I (our current iteration), and then reduce $$res[J] \times \binom{J}{I}$$ (the fixed res) from res[I]. Then we'll have the correct value for res[I].
But Mr. Author, how are we going to find res[K] in the first place? Let's first find out for a fixed K edges forest, in how ways we connect the remaining vertices to get a tree. Let's look at the components in the forest. Only their sizes are relevant because we can't connect anything inside them. Let the sizes be sz[0]... sz[N - 1]. (if you assume that the sizes are all 1, the number of resulting trees are NN - 2 (Kayley's theorem)).
To solve this subproblem, let's go to another subproblem. Let's assume that for every additional edge, we know which components it is going to go connect. Then, the number of resulting trees is $$\prod_{i=0}^{N-1} sz[i]^{d[i]}$$ where d[i] is the degree of component i (edges between this component and other components). The reason is that we have sz[v] vertices inside component v to give to every edge that has one endpoint in v.
Ok going back to the parent subproblem. d[i] huh? I've heard that vertex v appears in the Prufer code of a tree d[v] - 1 times. so we've gotta multiply the answer by sz[v] every time it appears in Prufer code. It's also multiplied by $$\prod_{i=0}^{N-1} sz[i]$$ because we haven't multiplied it one time (d[v] - 1 not d[v]). But how to make it get multiplied by sz[v] every time component v is chosen? Look at this product. (sz[0] + sz[1] + ... + sz[N - 1])N - 2. If in the i-th parenthesis sz[v] is chosen, then let the i-th place on the Prufer code of the tree connecting the components be the component v. The good thing about this product is that if component v has come in the Prufer code K times, then the multiplication of the parenthesis has sz[v]K in it. So it counts exactly what we want to count. $$( \prod_{i=0}^{N-1} sz[i] ) \times ( \sum_{i=0}^{N-1} sz[i] )^{N-2}$$ is the answer for some fixed K edges. $$\sum_{i=0}^{N-1}$$ corresponds to N in the original problem and N - 2 corresponds to Number_of_components - 2. so we want to count $$(\prod_{i=0}^{N-1}sz[i]) \times N^{number\_of\_components-2}$$
Okay Mr. Author so how do we count this for every K fixed edges in the original tree. Lets count dp[top_vertex v][size_of_component_containing_top_vertex s][the_number_of_edges_we_have_fixed e] which contains $$\prod_{i=0}^{N-1} sz[i]$$ of every component inside v's subtree which doesn't include v's component and Nthe_number_of_components_not_including_v's. We can update this from v's children. Let's add v's children one by one to the dp by assuming that the children we didn't go over don't exist in v's subtree.
let's go over old_dp[v][vs][ve] and dp[u][us][ue], we either fix the edge between u and v then it'll add dp[u][us][ue] × dp[v][vs][ve] to next_dp[v][us + vs][ve + ue + 1] and otherwise it'll add dp[u][us][ue] × dp[v][vs][ve] × N × us to dp[v][vs][ve + ue]. We can also divide it by N2 at the end with modulo inverses. We can find res[K] with the sum of dp[root][s][K] × s × N. (with s = N as a corner case).
The solution may look that it's N5 because it's inside 5 fors. But it's actually N4 if the us and vs fors go until sz[u] and sz[v] (actually only the subtree of v that we've iterated on). So the cost is sz[u] × sz[v] × N2. Let's look at it like every vertex from u's subtree is handshaking with every vertex of v's subtree and the cost of their handshaking is N2. We know that two vertices handshake only once. That's why it'll be $${ \binom { N } { 2 } } \times N ^ { 2 }$$ which is of $${\mathcal{O}}(N^{4})$$.
Solution #2:
Let's define F(X) as the number of spanning trees of the graph KN plus X - 1 copies of T (the original tree). If we look at F(X) we'll see that it is actually $${ \sum _ { i = 0 } ^ { N - 1 } X ^ { i } \times n u m b e r _ { o f } _ { t r e e s } _ { w i t h } _ { i } _ { c o m m o n } _ { e d g e s } _ { w i t h } _ { T } }$$ because it has Xi ways to choose which of the X multiple edges it should choose for the common edges. So the problem is to find F's coefficients. We can do that by polynomial interpolation if we have N sample answers of F. Let's just get N instances of F for X = 1 till X = N. We can find that using Kirchhoff's matrix tree theorem to find the number of spanning trees of a graph. So the complexity is $${ \mathcal { O } } ( i n t e r p o l a t i o n ) + { \mathcal { O } } ( D e t e r m i n a n t \times N )$$. So we have an $${\mathcal{O}}(N^{4})$$ complexity. This is how to do it in N2 -> (I don't know it yet, I'll update it when I have it ready)