원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
이진 트리
원제: 이진 트리
문제
모든 노드의 자식 노드가 0개 또는 2개인 이진 트리 에 대해 의 값은 다음과 같이 정의한다.
- 에서 노드 를 루트로 하는 서브 트리는, 와 의 자손 노드들로만 구성된 집합이다.
- 의 중위 순회 수열 는 를 중위 순회하면서 방문하는 노드들을 순서대로 나열한 수열로, 아래와 같이 정의할 수 있다.
- 의 루트 노드를 이라 하자. 을 하나로만 구성된 길이 1의 수열이라고 하자.
- 만약 의 자식 노드가 0개라면, 는 이다.
- 만약 의 자식 노드가 2개라면, 의 왼쪽 자식 노드를 루트로 하는 서브 트리가 , 의 오른쪽 자식 노드를 루트로 하는 서브 트리가 일 때, 는 , , 을 순서대로 이어붙인 수열이다.
- 의 리프 노드 개수를 라고 하자. 의 리프 노드들에 의 번호를 에서 나타나는 순서대로 (즉, 중위 순회 방문 순서대로) 붙였다고 하자.
- 의 서브 트리를 선택하면, 해당 서브 트리에 포함된 리프 노드들이 덮인다고 하자.
- 일 때, 는 리프 노드들 중 번호가 이상 이하인 리프 노드들만을 덮고 다른 리프 노드들은 덮지 않기 위해, 에서 선택해야 하는 최소 서브 트리 개수이다.
- 의 값은 인 모든 정수 순서쌍에 대한 의 합을 로 나눈 나머지이다.
예를 들어, 다음과 같은 이진 트리 가 있다고 가정해보자.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
의 값은 이다. 다음과 같이 서브 트리 두 개를 선택하면 5, 6, 7번 리프 노드만 덮이기 때문이다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
이런 식으로 모든 에 대해 의 값의 합은 47이고, 이를 로 나눈 나머지를 구하면 이다.
정수열 과 이 주어진다.
이진 트리 을 다음과 같이 정의한다.
- 은 노드가 개인 트리
- 는 루트의 왼쪽 자식 노드를 루트로 하는 서브 트리가 이고, 루트의 오른쪽 자식 노드를 루트로 하는 서브 트리가 인 트리 (, , )
을 구하는 프로그램을 작성하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- ()
- ()
부분문제
- (5점) (),
- (10점) ()
- (5점) , ()
- (10점) 의 노드 개수의 합은 이하
- (25점) 의 노드 개수의 합은 이하
- (45점) 추가 제약 조건 없음.
입력 형식
첫 번째 줄에 정수 이 주어진다.
다음 개의 줄 중 ()번째 줄에는 와 가 공백으로 구분되어 주어진다.
출력 형식
개의 줄을 출력한다. ()번째 줄에는 를 출력해야 한다.
예제
예제 1
5 0 0 1 0 1 2 3 1 4 4
3 7 21 47 254
위 예제에서 는 아래 그림과 같다.
(그림은 원문 PDF 탭에서 볼 수 있습니다.)
예제 2
7 0 0 1 1 2 2 3 3 4 4 5 5 6 6
3 13 65 337 1729 8641 41985