题目描述

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

输入描述

题解

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

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

1. 选择节点 $i$

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