Perfect Binary Trees
플래티넘 II의견: 0
*Note: The memory limit for this problem is 512MB, 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\).
Problem credits: Avnith Vijayram
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.
Problem credits: Avnith Vijayram
The first line contains an integer \(T\) (\(1 \leq T \leq 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 \leq u_i, v_i \leq 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\).
3
6
1 2
3 2
4 6
5 6
6 2
3
1 2
3 2
7
2 1
2 3
1 6
1 7
3 4
3 58
2
14In the first test case, Bessie can remove any of the following subsets of edges
to get a forest of perfect binary trees:
- \((2, 6)\)
- \((1, 2)\), \((2, 3)\), \((2, 6)\)
- \((1, 2)\), \((2, 3)\), \((4, 6)\)
- \((1, 2)\), \((2, 3)\), \((5, 6)\)
- \((1, 2)\), \((4, 6)\), \((5, 6)\)
- \((2, 6)\), \((4, 6)\), \((5, 6)\)
- \((2, 3)\), \((4, 6)\), \((5, 6)\)
- \((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\).
평가 및 의견
Perfect Binary Trees
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Perfect Binary Trees