题解

​ 观察可以发现，对于当前节点 $i$ ，从该节点所有子树中选出一些点后构成的节点集合的 LCA 一定是是节点 $i$ 。

这样子可以分成两种情况考虑:

1. 选择节点 $i$

   • 对于每棵子树可以任意选（可以是0）
   • 假设当前子树的节点数为 $cnt$ ，那么可选择的方案数为 $2 ^ {cnt}$ (可以用快速幂，或者预处理都行)

题目描述

最近公共祖先简称LCA(Lowest Common Ancestor)两个节点的最近公共祖先，就是这两个点的公共祖先里面离根最远的那个。 小红有一棵有根树，树的根节点为1号节点。定义$f(i)$是:LCA为$i$的非空节点集个数，小红想知道$f(1)$到$f(n)$的值。由于$f(i)$可能很大，因此你需要输出$f(i)$对$10^9+7$取模后的结果

输入描述

第一行输入一个正整数$n$，代表树的节点个数

接下来$n-1$行，每行两个整数$u,v(1\le u,v \le n)$表示树上的边。

$1≤ n ≤ 10^5$

输出描述

输出$n$个整数表示答案

样例

输入

3
1 2
2 3

输出

4 2 1

说明

LCA为1的节点集:(1),(1,2),(1,3),(1,2,3)

LCA为2的节点对:(2),(2,3)

LCA为3的节点对:(3)

输入

5
1 2
1 3
2 4
2 5

输出

23 5 1 1 1