#P1714. 2024.3.17-ZJTD-第三题-LCA

2024.3.17-ZJTD-第三题-LCA

题目描述

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

输入描述

第一行输入一个正整数nn,代表树的节点个数

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

1n1051≤ n ≤ 10^5

输出描述

输出nn个整数表示答案

样例

输入

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