P16574 [USACO26Open] Perfect Binary Trees

**Note: The memory limit for this problem is $512$MB, twice the default.** A **perfect binary tree** is a rooted tree where every non-leaf node has exactly two children and all leaf nodes are at an equal distance from the root. An **unrooted perfect binary tree** is an unrooted tree that is a perfect binary tree when rooted at one of its nodes. Bessie has a tree with $N$ ($1 \le N \le 10^5$) nodes. Determine the number of ways to remove a subset of edges from the tree so that the resulting forest is a collection of unrooted perfect binary trees. As the answer may be very large, output the result modulo $10^9 + 7$.

The first line contains an integer $T$ ($1 \le T \le 100$), the number of independent test cases. The first line of each test case contains an integer $N$. Each of the next $N - 1$ lines of each test case contains two integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$) indicating an edge between nodes $u_i$ and $v_i$. It is guaranteed that for each test case, the given edges form a tree with $N$ nodes. Additionally, the sum of $N$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, output a single integer: the number of subsets of edges that, when removed, result in a forest that is a collection of unrooted perfect binary trees, modulo $10^9 + 7$.

In the first test case, Bessie can remove any of the following subsets of edges to get a forest of perfect binary trees: 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)$ The first subset results in two subtrees of height $1$, the last subset results in six subtrees of height $0$, and the other subsets result in three subtrees of height $0$ and one subtree of height $1$. ### SCORING - Inputs $2$-$3$: $N \le 15$ - Inputs $4$-$5$: No node is adjacent to more than two other nodes. - Inputs $6$-$9$: $N \le 1000$, the sum of $N$ does not exceed $2000$, and no node is adjacent to more than three other nodes. - Inputs $10$-$13$: No node is adjacent to more than three other nodes. - Inputs $14$-$21$: No additional constraints.