UOJ Logo

NOI.AC

#68. 数叶子

统计

数叶子

给你一棵 $n$ 个点的无根树,点的编号是 $1-n$。叶子指的是一颗有根树没有孩子的结点。一个友善的叶子集合是由一些叶子组成的非空集合,且满足,这些叶子,在某种 dfs 顺序下(即存在一种 dfs 顺序),按 dfs 顺序取出所有叶子,友善的叶子集合里的叶子在这里面是连续的(顺序无所谓)。现在问你,当这棵树的根是 $i$ 的时候,一共有多少种友善的叶子集合。答案mod $10^9+7$。

输入格式

第一行一个数 $T$ 表示测试组数。

后面有 $T$ 组测试数据,对于每组数据:

第一行一个整数 $n$ 表示树的点数。

后面 $n-1$ 行每行两个数 $u,v$ 表示 $(u,v)$ 作为一条树边连接结点 $u,v$。

输出格式

按顺序输出每组数据的答案。

对每组测试数据:

输出 $n$ 行,第 $i$ 行一个整数,表示 $i$ 作为根时的答案,mod $10^9+7$。

样例1

输入

2
5
1 2
2 3
2 4
1 5
10
1 2
1 3
1 4
2 5
2 6
3 7
3 8
3 9
4 10

输出

7
7
3
3
3
63
63
63
51
31
31
31
31
31
31

样例2

样例数据

数据范围

20% $1\le T\le 10,2\le n\le 15$

60% $1\le T\le 10,2\le n \le 2000$

100% $1\le T\le 1000, 2\le n\le 200000,2\le \sum n\le 200000$