| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 10 | 4 | 4 | 50.000% |
Albert는 이진 트리 (binary tree)를 이용한 문제를 풀고 있다. $N$개의 노드를 가진 이진 트리 $T$의 노드에는 1부터 $N$까지 번호가 붙어있고, 편의상 길이가 $N$인 배열 2개를 이용하여 각 노드의 왼쪽 자식노드와 오른쪽 자식노드를 표현할 수 있다. 구체적으로 노드 $i$의 왼쪽 (오른쪽) 자식 노드를 $L[i]$ ($R[i]$)라 하고 자식 노드가 없을 경우에는 이 값이 0ドル$ 이라 정의하자.
예를 들어 아래 그림은 $N$ = 4 이고 $L = [2, 3, 0, 0],ドル $R = [4, 0, 0, 0]$인 경우를 나타낸다.
이 방법을 이용하면 임의의 이진 트리를 두 개의 배열로 표현할 수 있지만, 반대로 임의의 두 정수 배열이 언제나 올바른 이진 트리를 표현하지는 않는다. 이 문제에서 "올바른" 이진 트리란 $T$가 아래 조건을 모두 만족하는 경우를 말한다:
예를 들어 $L = [2, 0, 0, 0]$ 이고 $R = [0, 0, 0, 3]$인 경우 아래 처럼 두 개의 루트 노드가 있으므로 올바른 이진 트리가 아니다.
다른 예로, $L = [2, 1, 0, 0]$ 인 경우 $R$값에 관계 없이 노드1의 왼쪽 자식이 노드2이며 동시에 노드2의 왼쪽 자식이 1인 경우는 올바른 이진 트리가 아니다 - 이 경우 어떻게 하더라도 상기한 모든 조건을 만족할 수 없다.
Albert는 이를 이용한 새로운 문제를 생각해냈다: 입력으로 길이가 $N$인 두개의 정수 배열 $L$과 $R$이 주어졌을 때, 딱 한 쌍의 원소 값을 교환해서 얻은 새로운 배열이 올바른 이진 트리를 표현하는 경우가 몇 가지 있을까? 이 때, $L$ 배열의 한 쌍의 원소 값을 교환하거나 (즉, $i \neq j$ 일 때 $L[i]$ 와 $L[j]$ 값을 교환), $R$ 배열의 한 쌍의 원소 값을 교환하거나 (즉, $i \neq j$ 일 때 $R[i]$ 와 $R[j]$ 값을 교환), 혹은 $L$ 배열과 $R$ 배열의 원소 하나씩의 값을 교환할 수 있다 (즉, $L[i]$ 와 $R[j]$를 교환 - 이 때 $i = j$도 가능).
예를 들어 $N$ = 3 이고 $L = [2, 0, 0],ドル $R = [3, 0, 0]$인 경우, 아래와 같은 11가지 다른 방법으로 한 쌍의 원소 값을 교환하여 새로 얻은 배열이 올바른 이진 트리를 표현하도록 할 수 있다.
입력으로 길이가 $N$인 두개의 정수 배열 $L$과 $R$이 주어졌을 때, 임의의 한 쌍의 원소 값을 교환하여 얻은 새로운 배열이 올바른 이진트리가 되는 경우의 수를 구해보자.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 노드의 개수 $N$이 주어진다. 둘째 줄에 배열 $L$의 원소 값인 $N$개의 정수가 공백으로 구분되어 주어진다. 셋째 줄에 배열 $R$의 원소 값인 $N$개의 정수가 공백으로 구분되어 주어진다.
각 테스트 케이스의 정답을 각 줄에 출력한다.
7 6 0 5 6 2 0 3 0 0 0 0 0 1 7 0 0 1 7 4 3 5 0 0 6 0 0 0 0 2 2 0 0 0 4 0 3 0 0 2 1 4 0 4 2 1 4 0 0 0 0 0 4 2 3 4 0 0 0 0 0 4 2 3 0 0 4 0 0 0
12 0 4 0 8 16 20
예제 1: 추가 설명 없음
예제 2: 추가 설명 없음
예제 3: 아래와 같은 4가지 방법이 존재한다:
예제 4: 추가 설명 없음
예제 5: 입력으로 주어지는 $L,ドル $R$이 올바른 이진트리가 아니더라도 한 쌍의 원소값을 교환한 후에 올바른 이진트리를 얻을 수도 있음에 유의하자.
예제 6: 추가 설명 없음
예제 7: 추가 설명 없음