P17149 [ICPC 2017 Xi'an R] Island

作为 **珂朵莉学院** 的一员，你想奔赴战场去帮助珂朵莉。 天空中有 $n$ 座岛屿，你位于岛屿 $1$ 号。 初始时，存在 $n-1$ 条交通线，每条连接两座岛屿，使得任意两座岛屿之间均可互相到达。 然而，由于地面上野兽的不断攻击，每条交通线都有 $50\%$ 的概率被摧毁。 你想知道，在全部 $2^{n-1}$ 种可能的现实情况（每条交通线可能被摧毁或保留）中，有多少种现实能使你恰好到达 $k$ 座岛屿。答案可能很大，因此你只需要输出答案对 $1811939329$ 取模的结果。

输入包含多组测试数据。 第一行包含一个整数 $T$（$1 \le T \le 20$），表示测试数据的组数。 对于每组测试数据： 第一行包含一个整数 $n$（$1 \le n \le 10^5$）。 接下来的 $n-1$ 行，每行包含两个整数 $x$ 和 $y$，表示 $x$ 与 $y$ 之间有一条边。

对于每组测试数据，输出一行共 $n$ 个整数。 第 $k$ 个数表示能够恰好到达 $k$ 座岛屿的可能现实情况的数量。

翻译由 DeepSeek V4 Pro 完成