P11583 [KTSC 2022 R1] 进化
题目背景
**请使用 C++17 或 C++20 提交本题**
你需要在程序开头加入如下代码：
```cpp
#include
void init();
int analyze(int R);
void observation(int P);
```
题目译自 [2022년도 국제정보올림피아드 대표학생 선발고사 - 1차 선발고사](https://www.ioikorea.kr/archives/ioitst/2022/) T1「 [진화 ](https://assets.ioikorea.kr/ioitst/2022/1/evolution/evolution_statement.pdf)」
题目描述
你打算进行一项研究——对多种生物的进化过程进行探讨。除了最初的生物体外，所有其他生物体都是通过现有生物体的进化而诞生的。我们将现有的生物体称为父生物体，新诞生的生物体称为子生物体。
生物体通过进化诞生的过程可以用一个树形结构来表示，其中生物体是结点，进化过程是结接父生物体和子生物体的边。最初的生物体是树根。下图展示了一个这样的树形结构，其中 $1$ 号生物体进化出 $2$ 和 $3$ 号生物体，$2$ 号生物体进化出 $4$，$5$ 和 $6$ 号生物体，$3$ 号生物体进化出 $7$ 号生物体，$6$ 号生物体进化出 $8$ 和 $9$ 号生物体。
我们将这样的树形结构称为进化树。
对于每个有子生物体的生物体，我们将可能的进化路径分为主要进化和次要进化。
这种分类方法的效率可以通过进化复杂度来衡量。两个生物体 $A$ 和 $B$ 之间的进化复杂度定义为进化树中连接 $A$ 和 $B$ 的路径上经过的次要进化的数量。进化树的进化复杂度是所有生物体对之间进化复杂度的最大值。
进化越复杂，分析两个生物体之间的关联性就越困难。因此，我们需要通过适当的分类方法将进化树的进化复杂度最小化。
研究将持续 $N+Q$ 天。第一天，我们只发现了 $1$ 号生物体。接下来的每一天，我们将进行以下两种研究之一：
- 发现一个新的生物体，该生物体是现有生物体进化而来的。如果现有生物体的数量为 $T$，那么这个新生物体将被命名为 $T+1$ 号生物体。这种研究将进行 $N$ 次。
- 分析一个生物体及其通过 $0$ 次或多次进化而诞生的所有生物体。我们需要计算以该生物体为根的进化树的最小进化复杂度。每次分析是独立的，不会影响后续的分析。这种研究将进行 $Q$ 次。
你需要实现以下三个函数：
`
void init();
`
- 该函数在 `observation` 和 `analyze` 函数调用之前只会被调用一次。
`
void observation(int P);
`
- 该函数表示从编号为 $P$ 的生物体进化出一个新的生物体。当前发现的生物体数量为 $T$，新生物体编号为 $T+1$。
`
int analyze(int R);
`
- 该函数表示分析编号为 $R$ 的生物体及其通过 $0$ 次或多次进化而诞生的所有生物体。函数返回以 $R$ 号生物体为根的进化树的最小进化复杂度。
输入格式
示例评测程序按以下格式读取输入：
- 第 $1$ 行：$N'$
- 第 $i+1 (1 \leq i \leq N')$ 行：如果调用 `observation` 函数，则输入 `1 P`；如果调用 `analyze` 函数，则输入 `2 R`。
- $N' = N + Q$。
输出格式
示例评测程序按以下格式输出：
- 第 $i (1 \leq i \leq Q)$ 行：第 $i$ 次调用 `analyze` 函数的返回值。
说明/提示
### 样例解释 #1
评测程序将按以下顺序调用函数：
```cpp
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
```
下图展示了每次 `analyze` 调用时的进化树及其最佳分类方法之一。主要进化路径用粗线表示。
### 数据范围
对于所有输入数据，满足：
- $1 \leq N \leq 5\cdot 10^5$
- $1 \leq Q \leq 5\cdot 10^5$
详细子任务附加限制及分值如下表所示。
| 子任务 | 分值 | 约束 |
| :----------: | :----------: | :----------: |
|$1$|$7$|$N \leq 15,Q \leq 15$|
|$2$|$11$|$N \leq 3000,Q \leq 15$|
|$3$|$5$|第 $i (2 \leq i \leq N+1)$ 号生物体的父生物体是 $\left\lfloor\frac{i}{2}\right\rfloor$ 号生物体|
|$4$|$21$|每个生物体最多有 $2$ 个子生物体|
|$5$|$15$|$N \leq 3000,Q \leq 3000$|
|$6$|$41$|无附加限制|