25016번 - 진화 서브태스크언어 제한함수 구현

여러 생명체들을 대상으로 진화 과정을 다루는 연구를 진행하려고 한다. 최초 생명체를 제외한 모든 다른 생명체들은 기존에 존재하던 생명체가 진화하면서 새롭게 탄생하게 된다. 이 때, 기존에 존재하던 생명체를 부모 생명체, 새롭게 탄생한 생명체를 자식 생명체라고 정의한다. 

생명체들이 진화를 통해 탄생하는 과정은 생명체들을 정점, 진화 과정을 부모 생명체와 자식 생명체를 잇는 간선으로 나타내 최초 생명체를 루트로 한 트리 구조로 표현할 수 있다. 예를 들어, 아래 그림은 1번 생명체가 진화해 2, 3번 생명체가 탄생하고, 2번 생명체가 진화해 4, 5, 6번 생명체가 탄생하며, 3번 생명체가 진화해 7번 생명체가 탄생하며 6번 생명체가 진화해 8, 9번 생명체가 탄생하는 과정을 1번 생명체를 루트로 한 트리 구조로 표현한 것이다. 이러한 트리를 진화 트리라고 부르자.

자식 진화체가 존재하는 생명체 각각에 대해, 가능한 진화 방법들 중 하나의 진화 방법을 집중적으로 분석할 주요 진화, 나머지 진화 방법들을 부가 진화로 분류하려고 한다.

이러한 분류 방법의 효율성은 진화 복잡도를 측정하여 구할 수 있다. 두 생명체 A와 B 간의 진화 복잡도는 진화 트리에서 생명체 A와 B를 잇는 단순 경로 상에서 지나는 \underline{부가 진화}의 개수로 정의한다. 진화 트리의 진화 복잡도는 모든 생명체 쌍에 대한 진화 복잡도의 최댓값으로 정의한다. 

진화 복잡도가 커질수록 두 생명체들간의 연관성을 분석하기가 어려워지기에, 진화 트리의 진화 복잡도가 낮을수록 효율적인 방식이다. 따라서, 적절히 주요 진화와 부가 진화로 분류하여 진화 트리의 진화 복잡도를 최소화해야 한다.

$N+Q$일동안 연구를 진행한다. 연구를 진행하는 첫 날에는 1번 생명체의 발견만이 이루어져 있으며, 각 날에는 다음의 두 가지 연구 중 하나를 진행한다.

• 기존에 발견된 생명체에서 진화하여 탄생하는 새로운 생명체를 발견한다. 기존에 발견된 생명체의 수가 $T$였다면, 이 생명체는 $T+1$번 생명체로 명명한다. 이 연구는 $N$번 일어난다.
• 한 생명체에 대해, 해당 생명체에서 0번 이상의 진화를 거쳐 탄생하는 생명체들을 분석한다. 해당 생명체를 최초 생명체로 두어 만들어지는 진화 트리에 대해, 진화 트리의 진화 복잡도의 최솟값을 구해야 한다. 각 분석은 독립적이며, 이 분석에서 분류한 방법이 나중의 분석들에 영향을 미치지 않는다는 점에 유의하라. 이 연구는 $Q$번 일어난다.

해당 연구 계획을 진행하는 프로그램을 작성하여라.

여러분은 아래의 세 함수를 구현해야 한다.

void init()

• 이 함수는 observation 함수 및 analyze 함수가 호출되기 전 단 한 번만 호출된다.

void observation(int P)

• 이 함수는 인자로 주어지는 정수 P 및 현재 발견된 생명체의 수 $T$에 대해, P번 생명체에서 진화하여 탄생하는 새로운 $T+1$번 생명체가 발견되었음을 의미한다.

int analyze(int R)

• 이 함수는 인자로 주어지는 정수 R에 대해, R번 생명체 에서 0번 이상의 진화를 거쳐 탄생하는 생명체들을 분석한다는 것을 의미한다.
• 이 함수는 R번 생명체를 최초 생명체로 두어 만들어지는 진화 트리에 대해, 진화 트리의 진화 복잡도의 최솟값을 반환해야 한다.

제출하는 소스 코드의 어느 부분에서도 입출력 함수를 실행해서는 안 된다.

• $1 \le N \le 500\,000$
• $1 \le Q \le 500\,000$

• $N \le 15$
• $Q \le 15$

• $N \le 3000$
• $Q \le 15$

• $i$번 생명체의 부모 생명체는 $\lfloor \frac{i}{2} \rfloor$번 생명체다. $(2 \le i \le N+1)$

• 각 생명체의 자식 생명체는 최대 2개이다.

• $N \le 3000$
• $Q \le 3000$

• 추가적인 제약 조건이 없다.

그레이더는 다음 함수들을 순서대로 호출한다.

init()
observation(1)
observation(1)
observation(2)
observation(2)
observation(2)
observation(3)
analyze(1) = 2
observation(6)
analyze(2) = 2
observation(6)
analyze(6) = 1
analyze(1) = 2

아래 4개의 그림은 각 analyze 호출 시, 해당 분석에서 고려하는 진화 트리 및 최적의 분류 방법 중 하나를 의미한다. 주요 진화들이 굵게 표시되어 있다.

Sample grader는 아래와 같은 형식으로 입력을 받는다.

• Line 1: $N'$
• Line 1 + $i$ $(1 \le i \le N')$: observation 함수가 호출될 경우 1 P, analyze 함수가 호출될 경우 2 R

$N' = N + Q$를 만족한다.

Sample grader는 다음을 출력한다.

• Line $i$ $(1 \le i \le Q)$: $i$번째로 호출한 analyze 함수가 반환한 값

Sample grader는 실제 채점에서 사용하는 그레이더와 다를 수 있음에 유의하라.

• evolution_public.zip