문제 출제자 돕기

프로그래밍 대회 문제를 준비하는 데에는 많은 시간이 든다. 문제 설명과 모범 답안을 작성해야 할 뿐 아니라, 까다로운 입력 파일도 만들어야 한다. 이 문제에서는 어떤 과제의 입력을 만드는 일을 돕게 된다.

그 과제는 각 노드가 접근되는 확률이 주어졌을 때 최적 이진 탐색 트리를 찾는 문제이다. 여기서는 그 반대 문제를 푼다. 최적이 되어야 하는 트리가 주어졌을 때, 이 트리가 유일한 최적 이진 탐색 트리가 되도록 하는 접근 확률을 찾아야 한다. 필요한 정의는 모두 아래에 주어져 있다.

이진 탐색 트리는 다음과 같이 귀납적으로 정의된다.

• 노드가 하나도 없는 빈 트리는 이진 탐색 트리이다.
• 비어 있지 않은 모든 이진 탐색 트리는 정수 라벨을 가진 노드인 루트와, 그 루트의 왼쪽·오른쪽 서브트리인 두 개의 이진 탐색 트리로 이루어진다.
• 왼쪽 서브트리에는 라벨이 루트의 라벨보다 크거나 같은($\ge$) 노드가 하나도 없다.
• 오른쪽 서브트리에는 라벨이 루트의 라벨보다 작거나 같은($\le$) 노드가 하나도 없다.

노드를 찾을 때에는 다음 탐색 절차를 사용한다. 루트에서 시작한다. 현재 노드의 라벨을 찾으려는 라벨과 비교한다. 두 값이 같으면 원하는 노드를 찾은 것이다. 그렇지 않고 찾으려는 라벨이 더 작으면 왼쪽 서브트리에서, 더 크면 오른쪽 서브트리에서 계속 탐색한다.

노드의 접근 비용은 그 노드를 찾을 때까지 방문하는 노드의 수이다. 따라서 루트의 비용은 $1$, 루트 자식의 비용은 $2$와 같은 식으로 늘어난다. 트리의 기대 접근 비용은 $\sum_{i=1}^{n} p_i \cdot c_i$이며, 여기서 $p_i$는 라벨이 $i$인 노드의 접근 확률, $c_i$는 그 접근 비용이다. 최적 이진 탐색 트리는 기대 접근 비용이 최소인 트리이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 최적 이진 탐색 트리의 노드 수인 정수 $n$ ($1 \le n \le 50$)으로 시작한다. 노드의 라벨은 $1$부터 $n$까지의 정수이다. 이어지는 $n$개의 줄이 트리의 구조를 나타낸다. $i$번째 줄에는 두 정수가 있으며, 각각 라벨이 $i$인 노드의 왼쪽·오른쪽 서브트리의 루트 라벨이고, 빈 서브트리는 $-1$로 표시된다. 입력은 항상 올바른 이진 탐색 트리를 정의한다. 마지막 테스트 케이스 다음에는 $0$ 하나만 있는 줄이 오며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 한 줄에 $n$개의 정수를 출력한다. 라벨이 커지는 순서대로 각 노드의 접근 빈도를 나타낸다. 노드의 접근 확률은 그 빈도를 모든 빈도의 합으로 나눈 값이며, 이 빈도들은 주어진 트리를 유일한 최적 이진 탐색 트리로 만들어야 한다.

이 조건을 만족하는 빈도 배정은 여러 가지이므로, 답을 유일하게 정하기 위해 이 문제에서는 항상 유효한 하나의 표준 배정을 사용한다. 아래에서 위로 계산한다. 각 노드의 빈도는 $1$에 그 노드의 서브트리에 포함된 모든 노드의 빈도 합을 더한 값이다. 즉, 모든 리프의 빈도는 $1$이고, 모든 내부 노드의 빈도는 $1$에 그 노드의 모든 자손의 빈도 합을 더한 값이다. 이 빈도들을 라벨이 커지는 순서대로 출력한다.

이 규칙을 따르면 모든 빈도는 부호 있는 64비트 정수에 들어가는 양의 정수가 된다. $n \le 50$인 경우 어떤 값도 $2^{49}$을 넘지 않으며, 이는 $2^{63} - 1$보다 훨씬 작다.

예를 들어, 라벨이 $2$인 노드를 루트로 하고 라벨이 $1$과 $3$인 노드를 각각 왼쪽·오른쪽 자식으로 갖는 이진 탐색 트리는 다음과 같은 모양이다.

  2
 / \
1   3