진화
시간 제한2초메모리 제한1024 MB
정점을 하나씩 추가하며 자라는 트리에서, 질의마다 주어진 정점의 부분트리를 골라 주 진화를 정한 뒤 경로상 부가 진화 수의 최댓값이 가장 작아지는 값을 구합니다.
문제
여러 생명체를 대상으로 진화 과정을 다루는 연구를 진행하려고 한다. 최초 생명체를 제외한 모든 생명체는 기존에 존재하던 생명체가 진화하면서 새로 탄생한다. 이때 기존에 존재하던 생명체를 부모 생명체, 새로 탄생한 생명체를 자식 생명체라고 한다.
생명체가 진화를 통해 탄생하는 과정은 트리 구조로 나타낼 수 있다. 생명체를 정점으로, 부모 생명체와 자식 생명체를 잇는 진화 과정을 간선으로 하고, 최초 생명체를 루트로 둔다. 예를 들어 아래 그림은 1번 생명체가 진화해 2번과 3번 생명체가 탄생하고, 2번 생명체가 진화해 4번, 5번, 6번 생명체가 탄생하며, 3번 생명체가 진화해 7번 생명체가 탄생하고, 6번 생명체가 진화해 8번과 9번 생명체가 탄생하는 과정을 1번을 루트로 하는 트리로 나타낸 것이다. 이러한 트리를 진화 트리라고 부르자.
자식이 있는 생명체마다 가능한 진화 방법 중 하나를 골라 집중적으로 분석할 주요 진화로 정하고, 나머지 진화 방법은 부가 진화로 분류한다.
이 분류 방법의 효율은 진화 복잡도로 측정한다. 두 생명체 A와 B 사이의 진화 복잡도는 진화 트리에서 A와 B를 잇는 단순 경로 위에 있는 의 개수이다. 진화 트리의 진화 복잡도는 모든 생명체 쌍에 대한 진화 복잡도의 최댓값이다.
진화 복잡도가 커질수록 두 생명체의 연관성을 분석하기 어려워진다. 따라서 진화 트리의 진화 복잡도가 최소가 되도록 주요 진화와 부가 진화를 나누어야 한다.
연구는 일 동안 진행한다. 첫날에는 1번 생명체만 발견되어 있다. 각 날에는 다음 두 연구 중 하나를 진행한다.
- 기존에 발견된 생명체에서 진화하여 탄생하는 새로운 생명체를 발견한다. 기존에 발견된 생명체가 개였다면, 이 생명체를 번 생명체로 명명한다. 이 연구는 번 진행한다.
- 한 생명체를 골라, 그 생명체에서 0번 이상 진화를 거쳐 탄생하는 생명체들을 분석한다. 그 생명체를 최초 생명체로 하여 만들어지는 진화 트리에서 진화 복잡도의 최솟값을 구한다. 각 분석은 독립적이어서, 한 분석에서 정한 분류가 이후 분석에 영향을 주지 않는다. 이 연구는 번 진행한다.
이 연구 계획을 진행하는 프로그램을 작성하여라.