이진 검색 트리
시간 제한2초메모리 제한256 MB
0부터 N-1까지의 값을 삽입 순서대로 넣어 만든 이진 탐색 트리에서 모든 노드의 높이 합을 N이 최대 250000일 때 효율적으로 구하는 문제입니다.
문제
P는 길이가 N인 배열이며, 0 이상 N - 1 이하의 정수가 중복 없이 한 번씩 들어 있다. 이 배열의 원소를 순서대로 삽입하여 이진 검색 트리를 만든다. 이진 검색 트리는 루트를 가진 이진 트리이고, 각 노드에는 하나의 정수 값이 저장된다.
먼저 루트 노드를 만들고 P[0]을 저장한다. 그 뒤 P[1]부터 P[N-1]까지 다음 순서로 삽입한다.
for (int i = 1; i <= N - 1; i++) {
insert(root, P[i]);
}
insert 함수는 다음과 같이 동작한다.
void insert(Vertex V, int X) {
if (X < V에 저장된 수) {
if (V에 왼쪽 자식이 있으면) {
insert(V의 왼쪽 자식, X);
} else {
V의 왼쪽 자식을 새로 만들고 X를 저장한다.
}
} else {
if (V에 오른쪽 자식이 있으면) {
insert(V의 오른쪽 자식, X);
} else {
V의 오른쪽 자식을 새로 만들고 X를 저장한다.
}
}
}
노드의 높이는 루트에서 그 노드까지의 거리에서 1을 더한 값이다. N과 배열 P가 주어졌을 때, 위 방법으로 만든 이진 검색 트리의 모든 노드 높이의 합을 구하라.
입력
첫째 줄에 자연수 N이 주어진다. N은 250,000 이하이다. 이어지는 N개의 줄에는 P[0]부터 P[N-1]까지의 원소가 한 줄에 하나씩 주어진다.
배열 P에는 0 이상 N - 1 이하의 정수가 중복 없이 모두 들어 있다.
출력
주어진 배열 P로 이진 검색 트리를 만들었을 때, 모든 노드 높이의 합을 출력한다. 이 값은 2^63보다 작다.