| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 30 | 7 | 5 | 38.462% |
Bert 는 최근 이진 트리 (Binary Tree) 의 매력에 푹 빠져있다. 어떤 트리가 이진 트리이기 위해서는 각 노드의 자식이 최대 2개 이어야한다. 편의상 이진 트리 $T$ 의 노드는 1ドル$번부터 $N$ 번까지 번호가 붙어있으며, $i$번 노드의 왼쪽 자식은 $L_i,ドル 오른쪽 자식은 $R_i$ 로 표현한다 -- 자식이 없을 경우 이 값은 0이 된다.
예를 들어 아래 트리는 $N = 3,ドル $L = [2, 0, 0],ドル $R = [3, 0, 0]$ 인 경우를 나타내며 이 트리에서 루트는 1번 노드이다.
Bert 는 이진 트리 그리는 것을 좋아하는데, 우선 $V \ge N$ 인 적당히 큰 정수 $V$를 고정한 후, 아래 규칙에 따라 여러 가지 방법으로 그리는 것을 좋아한다. 편의상 노드 $i$ 의 정수 $x,y$ 좌표 값을 $(x_i, y_i)$ 라 하자.
위 조건을 모두 만족하는 $N$개의 좌표값을 정했다면 이진 트리를 그릴 수 있다고 하며, 두 이진 트리 그림이 있을 때, 같은 노드의 $x$ 좌표 값이 다르면 두 그림은 다른 방법으로 그려진 것이라 하자 (위 규칙대로면 각 노드의 $y$ 좌표 값은 항상 같다). 위 예제의 경우 $V = 4$ 라면 아래와 같은 4가지 다른 방법으로 이진 트리를 그릴 수 있다.
Bert는 임의의 이진 트리가 주어졌을 때 위 방법을 모두 지키면서 몇 가지 다른 방법으로 이진 트리를 그릴 수 있는지 궁금해졌다. 그런데 이를 지켜보던 Alice는 그 문제는 너무 쉽다며, 새로운 문제를 주었다:
예를 들어 $A = [0, 1, 0]$ 인 경우 앞서 살펴본 4개의 트리 중 $x_2 = 1$ 을 만족하는 좌측 3개의 방법으로 트리를 그릴 수 있다.
같은 트리에 대하여 만약 $A = [1, 0, 0]$ 인 경우, 조건을 만족하며 트리를 그릴 수 있는 방법이 없다 (앞서 살펴본바와 같이 4가지 방법으로 트리를 그릴 수 있지만, $x_1 = 1$ 인 경우는 불가능하다).
입력으로 $N, V$ 와 세 개의 정수 배열 $A, L, R$ 이 주어졌을 때, Alice의 조건을 만족하며 이진 트리를 그릴 수 있는 방법의 수를 구해보자.
입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, V$가 공백으로 구분되어 주어진다. 둘째 줄에는 배열 $A$가, 셋째 줄에는 배열 $L$이, 네번째 줄에는 배열 $R$이 주어지며, 각 줄의 배열은 공백으로 구분되어 $N$개의 정수가 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다. 단, 이 수가 매우 클 수 있으므로 444ドル,449円$로 나눈 나머지를 출력한다.
6 3 4 0 0 0 2 0 0 3 0 0 3 4 1 0 0 2 0 0 3 0 0 3 4 0 1 0 2 0 0 3 0 0 5 7 0 4 0 0 0 0 3 0 0 0 2 4 0 5 0 5 10 0 5 0 0 0 0 3 0 0 0 2 4 0 5 0 6 10 0 0 3 6 0 8 2 3 0 0 6 0 0 5 4 0 0 0
4 0 3 9 60 1
예제 1-3: 본문에서 다루었다.
예제 4-5: 추가 설명 없음.
예제 6: 아래 그림이 유일하게 조건을 만족하면서 이진 트리를 그릴 수 있는 방법이다. 그림 속 $x$ 배열의 값 중 밑줄이 쳐진 값들은 (3번, 4번, 6번) 노드의 좌표가 고정되어있음을 강조한다.