最近公共祖先简称LCA(Lowest Common Ancestor)两个节点的最近公共祖先,就是这两个点的公共祖先里面离根最远的那个。 塔子哥有一棵有根树,树的根节点为1号节点。定义f(i)是:LCA为i的非空节点集个数,塔子哥想知道f(1)到f(n)的值。由于f(i)可能很大,因此你需要输出f(i)对109+7取模后的结果
第一行输入一个正整数n,代表树的节点个数
接下来n−1行,每行两个整数u,v(1≤u,v≤n)表示树上的边。
1≤n≤105
输出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
扫码备注加群即可,期待您的到来~
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.