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 n2.)
Chef has found a tree with N nodes on day 0. On each of the next N-1 days, he's going to remove one edge. Let's denote the forest that remains after i days by Fi, for each 1 ≤ i ≤ N-1; also, let's denote the original tree by F0. On day i, Fi is created by randomly uniformly choosing one edge from Fi-1 and removing it.
Let Ei be the expected value of strength of the forest Fi, for each 0 ≤ i ≤ N-1. It can be proven that this number can be written in the form Pi / Qi, where gcd(Pi, Qi) = 1 and gcd(Qi, 109 + 7) = 1. Let Ri = Pi · Qi-1 mod 109 + 7, where Qi-1 denotes the modular inverse of Qi modulo 109 + 7.
Find the values of R0, R1, ..., RN-1.
- The first line of the input contains a single integer N — the number of nodes in the tree.
- N-1 lines follow. Each of these lines contains two space-separated integers u and v denoting an edge between nodes u and v in the tree.
Print a single line containing N space-separated integers R0, R1, ..., RN-1.
- 1 ≤ N ≤ 105
- 1 ≤ u, v ≤ N
Subtask #1 (25 points): 1 ≤ N ≤ 103
Subtask #2 (75 points): original constraints
Input: 5 1 2 1 3 2 4 2 5 Output: 25 16 333333346 7 5
|Tags||centroid-decomp, expected-value, fft, hard, jtnydv25, march18, probability|
|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|
Fetching successful submissions
If you are still having problems, see a sample solution here.