一、题目
题目内容
最近公共祖先简称 LCA(Lowest Common Ancestor) 两个节点的最近公共祖先，就是这两个点的公共祖先里面离根最远的那个。
小基有一棵有根树，树的根节点为 1 号节点。定义 f(i)f(i)f(i) 是：LCA 为 iii 的非空节点集个数，小基想知道 f(1)f(1)f(1) 到 f(n)f(n)f(n) 的值。由于 f(i)f(i)f(i) 可能很大，因此你需要输出 f(i)f(i)f(i) 对 109+710^9+7109+7 取模后的结果。
输入描述
第一行输入一个正整数 nnn，代表树的节点个数。
接下来 n−1n-1n−1 行，每行两个整数 u,v(1≤u,v≤n)u,v(1\le u,v \le n)u,v(1≤u,v≤n) 表示树上的边。
1≤n≤1051≤ n ≤ 10^51≤n≤105
输出描述
输出 nnn 个整数表示答案。
样例1
输入：
1 2 3 |
|
输出：
1 |
|
说明： LCA 为 1 的节点集：(1),(1,2),(1,3),(1,2,3) LCA 为 2 的节点对：(2),(2,3) LCA 为 3 的节点对：(3)
二、分析
这是一个关于计算树中各节点作为最近公共祖先（LCA）的非空节点集个数的问题。题目要求对于给定的一棵有根树（根节点为 1 号节点），计算每个节点 i 对应的 f(i)，即 LCA 为 i 的非空节点集的个数，并将结果对 10^9+7 取模后输出。
首先，我们需要理解 LCA 的概念。LCA 是指两个节点的公共祖先中离根最远的那个节点。在这个问题中，要计算每个节点作为 LCA 的情况个数，需要考虑所有可能的非空节点集，这些节点集的 LCA 正好是该节点。
接下来，考虑如何高效地计算每个节点的 f(i)。由于树的规模可能达到 1e5，常规的暴力枚举所有可能的节点集的方法显然不可行，时间复杂度会非常高。因此，我们需要寻找更高效的算法。一种可能的方法是利用树的结构和 LCA 的性质来进行动态规划或分治策略。例如，对于每个节点，我们可以考虑其子树中的节点集合，以及如何组合这些集合来计算以该节点为 LCA 的情况。
另外，可以观察到，一个节点作为 LCA 的情况，通常与其子节点的某些属性相关。比如，当一个节点的所有子节点都被包含在某个节点集中时，该节点可能成为这些子节点的 LCA。或者，当节点集中的节点分布在该节点的不同子树中时，该节点可能成为它们的 LCA。此外，还可以考虑使用倍增法或 Tarjan 算法等来预处理 LCA 问题，但这可能更多地用于查询两个节点的 LCA，而在这里我们需要统计所有可能的节点集的 LCA 情况，所以可能需要结合其他方法。
对于样例输入的分析，当输入为 3 个节点，构成一条链 1-2-3 时，输出的结果是 1、4、2、1。具体来说，f(1) 对应的节点集包括只包含 1 的情况，以及包含 1 和其子孙节点的各种组合，总共有 4 种情况；f(2) 对应的节点集包括只包含 2 的情况，以及包含 2 和其子孙节点 3 的情况，共有 2 种；f(3) 只有包含它自己的情况。在解决这个问题时，可能需要对每个节点计算其子树的大小以及某些组合数，或者利用容斥原理来计算以该节点为 LCA 的节点集数目。例如，对于节点 i，其所有子孙节点形成的集合中，某些组合的 LCA 可能是 i，这可能涉及到计算其各个子树的节点数，并通过组合数学的方法来统计这些情况
三、代码
以下是该问题的 Python 代码实现，基于动态规划的方法：
import sys
MOD = 10**9 + 7
def main():
n = int(sys.stdin.readline())
if n == 0:
print()
return
adj = [[] for _ in range(n + 1)]
for _ in range(n - 1):
u, v = map(int, sys.stdin.readline().split())
adj[u].append(v)
adj[v].append(u)
# 假设节点 1 是根
parent = [0] * (n + 1)
size = [0] * (n + 1)
depth = [0] * (n + 1)
dp = [0] * (n + 1)
# 使用 DFS 来计算每个节点的 size 和 dp
def dfs(u, p):
parent[u] = p
size[u] = 1
dp[u] = 1
for v in adj[u]:
if v != p:
dfs(v, u)
size[u] = (size[u] * (dp[v] + 1)) % MOD
dp[u] = (dp[u] + dp[v]) % MOD
# 添加当前节点本身的贡献
dp[u] = (dp[u] + 1) % MOD
dfs(1, 0)
# 计算每个节点的 f(i)
f = [0] * (n + 1)
f[1] = dp[1]
for u in range(2, n + 1):
# 计算 u 作为 LCA 的情况数
# 需要考虑其父节点和其他子树的贡献
v = parent[u]
# 恢复父节点的状态（因为父节点的 dp 和 size 已经被子节点 u 更新过）
# 这里需要逆向处理，以获得父节点在没有 u 子树时的状态
temp_size = size[v]
temp_dp = dp[v]
# 假设父节点 v 在没有子节点 u 时的 size 和 dp
size_without_u = size[v] * pow(dp[u] + 1, MOD - 2, MOD) % MOD
dp_without_u = (dp[v] - dp[u]) % MOD
# 计算 u 的贡献：父节点的其他子树的组合数乘以 u 的子树的组合数再加 1（考虑 u 单独存在的情况）
other_children = (size_without_u - 1) # 减去父节点自身
# 父节点的其他子树的组合数：prod(dp[其他子节点] + 1)
# 现在，假设父节点没有子节点 u，那么 size_without_u = product(dp[其他子节点] +1)
# 因此，other_children_combination = size_without_u
# 但是我们需要的是父节点其他子树的组合数（即没有 u 子树时的 size[v]，即 size_without_u）
# 所以 u 的贡献是 (size_without_u) * dp[u] + 1 （因为可以单独选 u）
# 或者是 (size_without_u) * (dp[u] + 1) - 1 （因为要排除空集的情况？）
# 这里需要仔细考虑组合情况：
# f(u) = (prod_{w 是 v 的其他子节点} (dp[w] +1 )) * (dp[u] +1 ) -1
# 这是因为，当 LCA 是 u 时，节点集合必须包含 u，并且可以包含 u 子树中的任意非空组合，
# 同时可以包含父节点其他子树中的任意组合（可以为空），但整个集合的 LCA 是 u。
# 但是父节点的其他子树中的节点如果被选中，那么它们的 LCA 可能是父节点或者其他节点。
# 所以可能需要另一种方法。
# 另一种思路：f(u) = (总的包含 u 的节点集数目) - sum_{祖先 v 的 f(v)} 中那些包含 u 的部分？
# 或者参考一些已有的 LCA 统计方法。
# 这里参考了一种方法：对于每个节点 u，其 f(u) 可以通过父节点的信息和其他兄弟节点的信息来计算。
# 具体来说，假设 u 的父节点是 p，那么 f(u) = (所有包含 u 的节点集合中，LCA 是 u 的数目)
# 这等于：（父节点 p 的其他子树的组合数） × （u 子树中的非空集合数目） × 2^（u 子树以外的兄弟子树的数目？）
# 或者可能需要更仔细的组合计算。
# 这里可能需要更准确的数学推导，但考虑到时间限制，我们采用动态规划的方法，
# 其中每个节点的 dp[u] 表示以 u 为根的子树中的节点集合数目，其中 LCA 是 u 的祖先中的一个。
# 或者，这里可能需要调整 dp 的定义。
# 在之前的样例中，当 u 是 2 时，其父节点是 1。父节点的其他子树是子节点 3。
# size_without_u 对于父节点 1 来说，是 size[1] / (dp[2] +1 ) → 即假设没有子节点 2 的情况下的 size。
# 例如，在样例中，size[1] 是 (dp[2]+1) * (dp[3]+1) = 2 * 2 =4。当去掉子节点 2 时，size_without_u 是 (4)/(2) =2，对应 dp[3]+1=2。
# 所以，当计算 f(u) 时，可以认为：
# f(u) = (其他兄弟子树的组合数（即 size_without_u） ) × (dp[u] +1 -1)
# 或者，其他兄弟子树的组合数乘以 u 子树中的非空集合数目。
# 其中，其他兄弟子树的组合数包括是否选择这些子树中的节点，但整个集合的 LCA 是 u。
# 所以，假设父节点 p 的其他子树的组合数是 s，那么对于 u 子树中的每个非空集合，
# 整体集合可以是这些非空集合加上父节点其他子树中的任意组合（可以为空），但 LCA 必须是 u。
# 这意味着父节点其他子树中的节点不能被选中，否则 LCA 可能是父节点或其他祖先。
# 这里可能需要重新审视 dp 数组的定义。或者参考其他方法。
# 另一种方法参考了组合贡献法：
# 对于每个节点 u，f(u) 是所有包含 u 的节点集合中，以 u 为最低公共祖先的数目。
# 这等于：所有包含 u 的集合中，所有元素的 LCA 是 u 的数目。
# 这等于：所有包含 u 的集合中，集合中的元素都位于 u 的子树中，并且至少有一个元素来自每个子树（除了可能的空子树），
# 或者其他条件？
# 这可能比较复杂。另一个思路是，当 u 是某个集合 S 的 LCA，则 S 中的所有元素都必须位于 u 的子树中，并且 S 中至少有两个元素分别来自 u 的不同子树，或者 S 中只有一个元素（即 u 本身）。
# 对于每个节点 u，其对应的 f(u) 包括：
# 1. 只包含 u 自己的集合：1 种。
# 2. 包含 u 和其子树中的其他节点，且这些节点分布在 u 的不同子树中。
# 所以，可以将 f(u) 分解为：
# f(u) = 1 （只包含 u） + sum_{选择至少两个不同子树的组合} 乘积 of 各个子树中的非空节点集数目。
# 例如，如果 u 有 k 个子节点，那么对于每个非空子集 mask（选择至少两个子树），计算各个选定子树的非空节点集数目的乘积，然后求和。再加上各个子树的非空节点集数目（当选择一个子树加上 u 的情况）。