레이팅 미적용*참고: 이 문제의 메모리 제한은 기본의 두 배인 512MB이다.*
포화 이진 트리(perfect binary tree)는 모든 리프가 아닌 노드가 정확히 두 개의 자식을 갖고 모든 리프 노드가 루트로부터 같은 거리에 있는 루트 트리이다.
루트 없는 포화 이진 트리는 어떤 노드를 루트로 삼았을 때 포화 이진 트리가 되는 루트 없는 트리이다.
베시는 \(N\) (\(1 \le N \le 10^5\))개의 노드를 가진 트리를 가지고 있다. 트리에서 간선의 부분집합을 제거하여 남은 포레스트가 루트 없는 포화 이진 트리들의 모음이 되도록 하는 방법의 수를 구하시오. 답이 매우 클 수 있으므로 \(10^9+7\)로 나눈 나머지를 출력한다.
문제 제공: Avnith Vijayram
채점 방식
- 입력 2-3: \(N\le 15\)
- 입력 4-5: 어떤 노드도 다른 노드 두 개보다 많은 노드와 인접하지 않는다.
- 입력 6-9: \(N\le 1000\), \(N\)의 합이 \(2000\)을 넘지 않으며, 어떤 노드도 다른 노드 세 개보다 많은 노드와 인접하지 않는다.
- 입력 10-13: 어떤 노드도 다른 노드 세 개보다 많은 노드와 인접하지 않는다.
- 입력 14-21: 추가 제약 조건이 없다.
문제 제공: Avnith Vijayram
첫째 줄에 독립적인 테스트 케이스의 수인 정수 \(T\) (\(1 \leq T \leq 100\))가 주어진다.
각 테스트 케이스의 첫째 줄에 정수 \(N\)이 주어진다.
각 테스트 케이스의 다음 \(N-1\)개의 줄 각각에 노드 \(u_i\)와 \(v_i\) 사이의 간선을 나타내는 두 정수 \(u_i\)와 \(v_i\) (\(1 \leq u_i, v_i \leq N\))가 주어진다.
각 테스트 케이스에서 주어진 간선들이 \(N\)개의 노드를 가진 트리를 이룸이 보장된다.
추가로, 모든 테스트 케이스에 대한 \(N\)의 합은 \(2\cdot 10^5\)를 넘지 않는다.
각 테스트 케이스마다 정수 하나를 출력한다: 제거했을 때 루트 없는 포화 이진 트리들의 모음인 포레스트가 되는 간선 부분집합의 수를 \(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\).