P16574 [USACO26Open] Perfect Binary Trees

**注意：本题的内存限制为 $512$MB，是默认限制的两倍。** **完美二叉树** 是一棵有根树，其中每个非叶结点恰好有两个孩子，且所有叶子结点到根的距离相等。 **无根完美二叉树** 是一棵无根树，当以它的某个结点为根时，它是一棵完美二叉树。 Bessie 有一棵包含 $N$（$1 \le N \le 10^5$）个结点的树。请计算有多少种删除树中边集的方法，使得得到的森林是由若干棵无根完美二叉树构成的集合。由于答案可能很大，请输出对 $10^9 + 7$ 取模的结果。

第一行包含一个整数 $T$（$1 \le T \le 100$），表示独立测试用例的数量。 每个测试用例的第一行包含一个整数 $N$。 接下来每个测试用例的 $N - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le N$），表示结点 $u_i$ 与 $v_i$ 之间的一条边。 保证对于每个测试用例，给出的边构成一棵包含 $N$ 个结点的树。 此外，所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数：删除边集后，得到的森林是由无根完美二叉树构成的集合的方案数，对 $10^9 + 7$ 取模。

在第一个测试用例中，Bessie 可以删除以下任意边集，使得得到的森林由完美二叉树构成： 1. $(2, 6)$ 2. $(1, 2), (2, 3), (2, 6)$ 3. $(1, 2), (2, 3), (4, 6)$ 4. $(1, 2), (2, 3), (5, 6)$ 5. $(1, 2), (4, 6), (5, 6)$ 6. $(2, 6), (4, 6), (5, 6)$ 7. $(2, 3), (4, 6), (5, 6)$ 8. $(1, 2), (2, 3), (2, 6), (4, 6), (5, 6)$ 第一个边集得到两棵高度为 $1$ 的子树，最后一个边集得到六棵高度为 $0$ 的子树，其余边集得到三棵高度为 $0$ 的子树和一棵高度为 $1$ 的子树。 ### 计分规则 - 输入 $2$-$3$：$N \le 15$ - 输入 $4$-$5$：没有结点的度数超过 $2$。 - 输入 $6$-$9$：$N \le 1000$，所有测试用例的 $N$ 之和不超过 $2000$，且没有结点的度数超过 $3$。 - 输入 $10$-$13$：没有结点的度数超过 $3$。 - 输入 $14$-$21$：无额外限制。 翻译由 DeepSeek V4 Pro 完成