Chef Cuts Tree

All submissions for this problem are available.
Read problems statements in Mandarin chinese, Russian and Vietnamese as well.
A forest is an undirected acyclic graph. Let us define the strength of a forest as the sum of squares of sizes of its connected components. (Clearly, a tree with n nodes has strength n^{2}.)
Chef has found a tree with N nodes on day 0. On each of the next N1 days, he's going to remove one edge. Let's denote the forest that remains after i days by F_{i}, for each 1 ≤ i ≤ N1; also, let's denote the original tree by F_{0}. On day i, F_{i} is created by randomly uniformly choosing one edge from F_{i1} and removing it.
Let E_{i} be the expected value of strength of the forest F_{i}, for each 0 ≤ i ≤ N1. It can be proven that this number can be written in the form P_{i} / Q_{i}, where gcd(P_{i}, Q_{i}) = 1 and gcd(Q_{i}, 10^{9} + 7) = 1. Let R_{i} = P_{i} · Q_{i}^{1} mod 10^{9} + 7, where Q_{i}^{1} denotes the modular inverse of Q_{i} modulo 10^{9} + 7.
Find the values of R_{0}, R_{1}, ..., R_{N1}.
Input
 The first line of the input contains a single integer N — the number of nodes in the tree.
 N1 lines follow. Each of these lines contains two spaceseparated integers u and v denoting an edge between nodes u and v in the tree.
Output
Print a single line containing N spaceseparated integers R_{0}, R_{1}, ..., R_{N1}.
Constraints
 1 ≤ N ≤ 10^{5 }
 1 ≤ u, v ≤ N
Subtasks
Subtask #1 (25 points): 1 ≤ N ≤ 10^{3}
Subtask #2 (75 points): original constraints
Example
Input: 5 1 2 1 3 2 4 2 5 Output: 25 16 333333346 7 5
Author:  jtnydv25 
Editorial  https://discuss.codechef.com/problems/CUTTREE 
Tags  centroiddecomp, expectedvalue, fft, hard, jtnydv25, march18, probability 
Date Added:  31122017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions