2 × n 격자 임베딩의 개수

시간 제한4초메모리 제한512 MB

요약

라벨이 붙은 트리의 각 노드를 2행 n열 격자에 배치하되 노드 1은 왼쪽 위 칸에 놓고, 변으로 이어진 두 노드는 서로 맞닿으며, 같은 칸을 쓰지 않도록 하는 임베딩의 수를 10^9+7로 나눈 나머지를 구한다.

난이도: 어려움10점 중 8점
유형: 트리, DFS, 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

트리는 정점 $n$ 개와 무방향 간선 $n-1$ 개로 이루어진 그래프이고, 어떤 두 정점 사이에도 경로가 정확히 하나 있다. 라벨 트리는 정점마다 1 이상 $n$ 이하의 정수가 서로 다르게 하나씩 붙은 트리다. 트리를 보기 좋게 그리기는 대체로 어렵지만, 직사각형 격자에 깔끔하게 담기는 트리도 있다.

정점이 $n$ 개인 라벨 트리 $G$ 가 있다. $G$ 의 $2 \times n$ 임베딩은 $G$ 의 정점을 2행 $n$ 열 격자의 칸에 대응시키는 함수이고, 다음 세 조건을 모두 만족한다.

정점 1은 왼쪽 위 모서리 칸에 대응한다.
간선으로 이어진 두 정점은 위, 아래, 왼쪽, 오른쪽으로 맞닿은 두 칸에 대응한다.
서로 다른 두 정점은 같은 칸에 대응하지 않는다.

주어진 트리의 $2 \times n$ 임베딩 개수를 $10^9 + 7$ 로 나눈 나머지를 구하라.

입력

첫째 줄에 $G$ 의 정점 개수 $n$ 이 주어진다. ( $1 \le n \le 300\,000$ )

이어지는 $n-1$ 개 줄 중 $j$ 번째 줄에는 $j$ 번째 간선의 두 끝점 $a_j$ 와 $b_j$ 가 주어진다. ( $1 \le a_j, b_j \le n$ , $a_j \ne b_j$ )

입력으로 주어지는 그래프는 항상 트리다.

출력

주어진 트리의 $2 \times n$ 임베딩 개수를 $10^9 + 7$ 로 나눈 나머지를 한 줄에 출력한다.

힌트

위 그림은 첫 번째 예제에 주어진 트리의 임베딩 4개를 모두 그린 것이다.

예제3

예제 1
입력
```
5
1 2
2 3
2 4
4 5
```
예상 출력
```
4
```
예제 2
입력
```
1
```
예상 출력
```
1
```
예제 3
입력
```
2
2 1
```
예상 출력
```
2
```