레드-블랙 트리

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

요약

빈 자식 자리에 가상 리프를 붙인 이진 트리의 정점을 빨강과 검정으로 칠하는 방법 중 레드-블랙 트리 조건을 만족하는 개수를 10^9+7로 나눈 나머지로 구합니다.

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

문제

표준 라이브러리 대부분은 집합(set) 자료구조를 구현할 때 레드-블랙 트리를 사용한다. 이 문제에서는 주어진 이진 트리의 정점을 색칠해서 레드-블랙 트리가 되도록 하는 방법의 수를 구한다. 답은 $10^9 + 7$ 로 나눈 나머지로 출력한다.

이진 트리에서 자식이 둘보다 적은 정점에는 빠진 자식의 자리마다 가짜 정점을 추가한다. 다음 조건을 모두 만족하면 레드-블랙 트리이다.

각 정점은 빨간색 또는 검은색 중 하나로 칠한다.
루트와 추가된 가짜 정점은 검은색이다.
빨간 정점의 부모는 검은색이다.
루트에서 모든 가짜 잎까지의 경로에 포함된 검은 정점의 수가 모두 같다.

검은 정점의 부모는 검은색일 수 있다. 정점 하나라도 색이 다르면 두 칠하기 방법은 서로 다른 것이다.

입력

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

다음 $n$ 개의 줄에 트리가 주어진다. $i$ 번째 줄에는 $i$ 번 정점의 왼쪽 자식 $l_i$ 와 오른쪽 자식 $r_i$ 가 주어진다. 자식이 없으면 0이다. $l_i = 0$ 또는 $i < l_i \le n$ 이고, $r_i = 0$ 또는 $i < r_i \le n$ 이다. 루트는 1번 정점이다. 입력은 항상 올바른 트리이다.

출력

주어진 트리를 올바른 레드-블랙 트리로 만드는 칠하기 방법의 수를 $10^9 + 7$ 로 나눈 나머지로 출력한다.

예제2

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