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

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

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

(a) 만든 트리	(b) 리프 노드에 번호를 붙인 트리

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

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

정수열 \(A_1, A_2, \cdots , A_N\)과 \(B_1, B_2, \cdots , B_N\)이 주어진다.

이진 트리 \(T_0, T_1, \cdots , T_N\)을 다음과 같이 정의한다.

• \(T_0\)은 노드가 \(1\)개인 트리
• \(T_i\) 는 루트의 왼쪽 자식 노드를 루트로 하는 서브 트리가 \(T_{A_i}\)이고, 루트의 오른쪽 자식 노드를 루트로 하는 서브 트리가 \(T_{B_i}\)인 트리 (\(1 ≤ i ≤ N\), \(0 ≤ A_i ≤ i - 1\), \(0 ≤ B_i ≤ i - 1\))

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

• 주어지는 모든 수는 정수이다.
• \(1 \le N \le 100\,000\)
• \(0 \le A_i \le i - 1\) (\(1 \le i \le N\))
• \(0 \le B_i \le i - 1\) (\(1 \le i \le N\))

첫 번째 줄에 정수 \(N\)이 주어진다.

다음 \(N\)개의 줄 중 \(i\) (\(1 ≤ i ≤ N\))번째 줄에는 \(A_i\)와 \(B_i\)가 공백으로 구분되어 주어진다.

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

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2024 > 1차 대회 > 중등부 3번 / 고등부 2번