P17149 [ICPC 2017 Xi'an R] Island

As a member of The Academy of Chtholly, you want to rush to the battle field to help Chtholly. There are $n$ islands in the sky, and you are in island number $1$. At first, there are $n-1$ transportation lines, each connecting two islands, making each two islands reachable. However, due to the continues attack of the beasts on the ground, each transportation line has $50\%$ possibility of being destroyed. You want to find, in all $2^{n-1}$ possible realities (each transportation line may be destroyed or not), how many of them you can reach exactly $k$ islands. The answer may be large, so you just need to output the answer mod $1811939329$.

The input contains multiple test cases. The first line contains a number $T$ ($1 \le T \le 20$) denoting the number of test cases. In each test case: The first line contains a number $n$ ($1 \le n \le 10^5$). The following $n-1$ lines each contains two numbers $x$, $y$ denoting that there is an edge between $x$ and $y$.

For each test case, output one line containing $n$ numbers. The $k$-th number is the number of possible realities that you can reach exactly $k$ islands.