루미 알고리즘

#1096골드이진 트리이진 트리

KOI 2024 1차코딩중등부 3번, 고등부 2번출제 박수찬이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

이진 트리

원제: 이진 트리

문제

모든 노드의 자식 노드가 0개 또는 2개인 이진 트리 TT에 대해 S(T)S(T)의 값은 다음과 같이 정의한다.

  • TT에서 노드 uu를 루트로 하는 서브 트리는, uu와 uu의 자손 노드들로만 구성된 집합이다.
  • TT의 중위 순회 수열 p(T)p(T)는 TT를 중위 순회하면서 방문하는 노드들을 순서대로 나열한 수열로, 아래와 같이 정의할 수 있다.
    • TT의 루트 노드를 rr이라 하자. [r][r]을 rr 하나로만 구성된 길이 1의 수열이라고 하자.
    • 만약 rr의 자식 노드가 0개라면, p(T)p(T)는 [r][r]이다.
    • 만약 rr의 자식 노드가 2개라면, rr의 왼쪽 자식 노드를 루트로 하는 서브 트리가 XX, rr의 오른쪽 자식 노드를 루트로 하는 서브 트리가 YY일 때, p(T)p(T)는 p(X)p(X), [r][r], p(Y)p(Y)을 순서대로 이어붙인 수열이다.
  • TT의 리프 노드 개수를 kk라고 하자. TT의 리프 노드들에 1,2,⋯ ,k1, 2, \cdots, k의 번호를 p(T)p(T)에서 나타나는 순서대로 (즉, 중위 순회 방문 순서대로) 붙였다고 하자.
  • TT의 서브 트리를 선택하면, 해당 서브 트리에 포함된 리프 노드들이 덮인다고 하자.
  • 1≤a≤b≤k1 \le a \le b \le k일 때, f(a,b)f(a, b)는 리프 노드들 중 번호가 aa 이상 bb 이하인 리프 노드들만을 덮고 다른 리프 노드들은 덮지 않기 위해, TT에서 선택해야 하는 최소 서브 트리 개수이다.
  • S(T)S(T)의 값은 1≤a≤b≤k1 \le a \le b \le k인 모든 (a,b)(a, b) 정수 순서쌍에 대한 f(a,b)f(a, b)의 합을 109+710^9 + 7로 나눈 나머지이다.

예를 들어, 다음과 같은 이진 트리 TT가 있다고 가정해보자.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

f(5,7)f(5, 7)의 값은 22이다. 다음과 같이 서브 트리 두 개를 선택하면 5, 6, 7번 리프 노드만 덮이기 때문이다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

이런 식으로 모든 1≤a≤b≤71 \le a \le b \le 7에 대해 f(a,b)f(a, b)의 값의 합은 47이고, 이를 109+710^9 + 7로 나눈 나머지를 구하면 S(T)=47S(T) = 47이다.

정수열 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N과 B1,B2,⋯ ,BNB_1, B_2, \cdots, B_N이 주어진다.

이진 트리 T0,T1,⋯ ,TNT_0, T_1, \cdots, T_N을 다음과 같이 정의한다.

  • T0T_0 은 노드가 11개인 트리
  • TiT_i 는 루트의 왼쪽 자식 노드를 루트로 하는 서브 트리가 TAiT_{A_i}이고, 루트의 오른쪽 자식 노드를 루트로 하는 서브 트리가 TBiT_{B_i}인 트리 (1≤i≤N1 \le i \le N, 0≤Ai≤i−10 \le A_i \le i - 1, 0≤Bi≤i−10 \le B_i \le i - 1)

S(T1),S(T2),⋯ ,S(TN)S(T_1), S(T_2), \cdots, S(T_N)을 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 1≤N≤100 0001 \le N \le 100\,000
  • 0≤Ai≤i−10 \le A_i \le i - 1 (1≤i≤N1 \le i \le N)
  • 0≤Bi≤i−10 \le B_i \le i - 1 (1≤i≤N1 \le i \le N)

부분문제

  1. (5점) Ai=Bi=i−1A_i = B_i = i - 1 (1≤i≤N1 \le i \le N), N≤10N \le 10
  2. (10점) Ai=Bi=i−1A_i = B_i = i - 1 (1≤i≤N1 \le i \le N)
  3. (5점) Ai=i−1A_i = i - 1, Bi=0B_i = 0 (1≤i≤N1 \le i \le N)
  4. (10점) T1,T2,⋯ ,TNT_1, T_2, \cdots, T_N의 노드 개수의 합은 1 0001\,000 이하
  5. (25점) T1,T2,⋯ ,TNT_1, T_2, \cdots, T_N의 노드 개수의 합은 300 000300\,000 이하
  6. (45점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정수 NN이 주어진다.

다음 NN개의 줄 중 ii (1≤i≤N1 \le i \le N)번째 줄에는 AiA_i와 BiB_i가 공백으로 구분되어 주어진다.

출력 형식

NN개의 줄을 출력한다. ii (1≤i≤N1 \le i \le N)번째 줄에는 S(Ti)S(T_i)를 출력해야 한다.

예제

예제 1

입력
5
0 0
1 0
1 2
3 1
4 4
출력
3
7
21
47
254

위 예제에서 T4T_4는 아래 그림과 같다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

예제 2

입력
7
0 0
1 1
2 2
3 3
4 4
5 5
6 6
출력
3
13
65
337
1729
8641
41985

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.