时间限制： 2.0 秒

空间限制： 512 MB

题目背景

在以 $r$ 为根的二叉树中，任一节点 $v$ 与 $r$ 之间通路上的所有节点（包含 $r$ 和 $v$ 自身）都称为 $v$ 的祖先。如果节点 $a$ 同时是 $v$ 和 $u$ 的祖先，则称作 $v$ 和 $u$ 的公共祖先。显然，$r$ 是所有节点的公共祖先。在两点公共祖先中深度最大的节点，即为最近公共祖先（Lowest Common Ancestor）。

题目描述

在一个 $n$ 个节点二叉树，节点编号为 $1,2,\cdots,n$，每个节点只记录了父节点的指针。

请设计一个算法，对任意两个节点 $x$ 和 $y$ 找到他们的最近公共祖先。要求：

• 时间和空间复杂度均不能超过 $O(\text{dep}(x)+\text{dep}(y))$，具体限制我们将在交互库做说明。
• 允许使用基本数据结构。

交互方式

这是一道函数式交互题，不需要选手考虑输入输出，也不要从标准输入读入数据，或将任何内容输出到标准输出，否则会影响判题。

你提交的代码需要包含头文件 lca.h。

你需要实现一个函数 int lca(int x, int y)。给定树上两个节点的编号，返回他们最近公共祖先的节点编号。

你可以调用以下函数：

int getFa(int u);

输入一个节点编号，获取其父亲。当一个节点为根节点时，其父亲编号返回 $0$。

需要注意，每次查询调用 getFa 的次数有严格的限制。设根节点的深度为 $1$，则调用次数不得超过 $2\times(\text{dep}(x)+\text{dep}(y))$。

本题中的树结构，保证编号 1 的节点为根，$i$ 号节点的父亲 $f_i$ 保证 $1\le f_i<i$。

以下我们给出一个代码提交实例（固定返回树根的编号 1，仅作为可以通过编译的示例，不保证能得分）。

#include "lca.h"
int lca(int x, int y)
{
    return 1;
}

白盒交互库实例

具体请见附加文件区的 interactor.cc 和 lca.h。本题直接采用白盒交互库进行评测。

如果你本地的实现代码为 main.cc，则将交互库放在同一目录下，在 Linux 系统中输入以下命令行即可运行：

g++ main.cc interactor.cc -Wall -std=c++20 -o foo -lm -O2 -I/include

在 Windows 下会生成 foo.exe，在 Linux 下会生成 foo，你可以输入 .\foo.exe 或者 ./foo 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

交互库会先读入节点个数、查询次数，再读入树结构（$2\sim n$ 的父亲编号，证每个 $f_i$ 不会出现超过 $2$ 次。我们约定 $f_i$ 第一次出现时，表示 $i$ 是 $f_i$ 的左儿子；$f_i$ 第二次出现时，表示 $i$ 是 $f_i$ 的右儿子。）。每次查询给出两个编号，以及本次查询调用 getFa 次数的限制，输出一行一个整数为 LCA 节点的编号。

6 3
1 2 2 1 5
3 4 12
3 3 12
2 6 10

2
3
1

样例 1 解释

样例给出的二叉树如图。

子任务

对于所有数据，保证节点个数和查询个数有 $n,q\le 10^6$，所有节点的深度不超过 $100$，输入的树一定是一个二叉树结构。

本题无数据梯度，需要通过全部数据获得所有分数。

来源

清华《数据结构》期末 2022 秋 / 2023 水木清研模拟题