푸드 파이트 - Problem

Busy Beaver가 다시 한번 농산물 시장에 혼란을 일으키고 있습니다! 이번에는 가판대 사이에서 음식 싸움을 시작했습니다.

가판대는 $1$부터 $N$까지 번호가 매겨져 있으며, $N-1$개의 도로로 연결되어 트리를 이룹니다. 즉, 도로를 따라 임의의 가판대에서 다른 가판대로 이동할 수 있으며, 임의의 두 가판대 사이에는 정확히 하나의 단순 경로가 존재합니다.

Busy Beaver는 다음과 같이 각 가판대를 Team Potato 또는 Team Tomato에 할당합니다:

그는 가판대 $1$에서 시작하여 도로를 따라 이동하며 모든 가판대를 방문하고, 마지막에 가판대 $1$로 돌아옵니다. 이러한 모든 경로 중에서, 그는 이동한 총 도로 수가 최소가 되는 경로를 하나 선택합니다.
가판대 $1$은 Team Potato에 할당됩니다.
Busy Beaver가 (가판대 $1$을 제외하고) 처음으로 가판대를 방문할 때마다, 그는 즉시 해당 가판대를 두 팀 중 하나에 할당합니다. 공정한 싸움을 위해, 그는 새로운 가판대를 할당할 때마다 팀 할당을 번갈아 가며 수행합니다. 즉, 가장 최근에 할당된 가판대가 Team Potato에 할당되었다면, 다음에 새로 방문하는 가판대는 반드시 Team Tomato에 할당되어야 하며, 그 반대도 마찬가지입니다.

여러분의 임무는 가능한 팀 할당의 수를 세는 것입니다. 서로 다른 최소 길이 경로가 동일한 최종 할당을 생성할 수 있으며, 이러한 할당은 한 번만 계산해야 한다는 점에 유의하십시오. 답이 매우 클 수 있으므로 $10^9 + 7$로 나눈 나머지를 출력하십시오.

첫 번째 줄에는 테스트 케이스의 수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스의 첫 번째 줄에는 정수 $N$ ($2 \le N \le 10^5$)이 주어집니다.

다음 $N-1$개의 줄에는 각각 두 정수 $u$와 $v$ ($1 \le u, v \le N, u \neq v$)가 주어지며, 이는 가판대 $u$와 $v$ 사이에 도로가 있음을 나타냅니다.

모든 테스트 케이스에 대한 $N$의 합은 $2 \cdot 10^5$를 넘지 않습니다.

각 테스트 케이스마다 가능한 최종 팀 할당의 수를 $10^9 + 7$로 나눈 나머지를 출력하십시오.

이 문제에는 두 가지 서브태스크가 있습니다.

(10점): 가판대들이 가판대 $1$을 루트로 하는 스타 그래프를 이룹니다. 더 구체적으로, 가판대 $1$에는 $N-1$개의 도로가 연결되어 있습니다.
(20점): 가판대들이 가판대 $1$을 루트로 하는 이진 트리를 이룹니다. 더 구체적으로, 가판대 $1$에는 최대 2개의 도로가 연결되어 있고, 다른 모든 가판대에는 최대 3개의 도로가 연결되어 있습니다.
(70점): 추가 제약 조건이 없습니다.

예제에는 4개의 테스트 케이스가 포함되어 있습니다:

첫 번째 테스트 케이스에서 가능한 팀 할당 중 하나는 아래와 같습니다.

최소 길이 경로 중 하나는 다음과 같습니다: $1 \to 2 \to 3 \to 2 \to 4 \to 2 \to 1$.

이 경로의 총 길이는 6이며, 이는 가판대 $1$에서 시작하여 모든 가판대를 방문하고 가판대 $1$로 돌아오는 경로 중 가장 짧은 것입니다.

가판대는 처음 방문한 순서대로 할당됩니다:

다른 가능한 팀 할당은 가판대 $3$보다 가판대 $4$를 먼저 방문함으로써 얻어지며, 이는 팀을 서로 바꿉니다. 따라서 가능한 총 팀 할당 수는 2입니다.

QOJ.ac