时间限制： 1.0 秒

空间限制： 30 MB

题目背景

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

题目描述

给定一个由 $n$ 个节点组成的二叉树，各节点的关键码都是来自 $0,1,\cdots,n-1$ 的自然数，且彼此互异。

尽管你不能直接访问该树，但其先序，后序遍历序列已分别记录在数组 $p_0,\cdots,p_{n-1}$ 和 $q_0,\cdots,q_{n-1}$ 中。

请设计一个算法，对 $0,1,\cdots n-1$ 范围内的任意一对整数关键码 $x$ 和 $y$，找出他们对应节点的最近公共祖先，并输出其关键码。要求算法的运行时间和辅助空间均不超过 $O(n)$。

特别地，本题的交互库已经使用了 $O(n)$ 的辅助空间，因此你在本提交窗口提交的代码辅助空间必须为 $O(1)$。

Honor Code

我们在原则上不允许直接访问树结构，或者利用函数结构将树显式的构造出来。但是由于部署较为麻烦（懒得弄了，又不是什么正式比赛 QAQ），我们只对空间做了限制，并没有完全封死显式构造树后通过本题的可能性。

因此我们只口头倡议，不建议采用此做法通过本题，或者只使用这种方法进行对拍/验证数据的正确性。反正在初试真这么写，总计 20 分的算法大题就没有分了，对自己负责就行。

交互方式

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

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

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

你可以调用以下函数：

int getTreeSize();
int getPrePos(int v);
int getPostPos(int v);
int getPreNum(int p);
int getPostNum(int p);

分别代表以下内容：

• getTreeSize()：获取树的节点个数 $n$
• getPrePos(v) 和 getPostPos(v)：根据关键码，获取其在前序遍历/后序遍历序列中的位置。传入的参数和返回的值应当均为介于 $0$ 到 $n-1$ 的非负整数。
• getPreNum(p) 和 getPostNum(p)：给定序列位置，返回前序遍历/后序遍历序列对应位置的关键码的值。传入的参数和返回的值应当均为介于 $0$ 到 $n-1$ 的非负整数。

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

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

白盒交互库实例

具体请见附加文件区的 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 命令行执行该文件。或者将交互库接口与你实现的函数统一在单代码文件中进行本地调试即可。

交互库会先读入节点个数、查询次数，再读入前序遍历序列、后序遍历序列。每次查询给出两个关键码，输出一行一个整数为 LCA 节点的关键码。

11 3
3 0 8 5 2 6 7 10 4 1 9
5 8 2 0 10 4 7 9 1 6 3
2 5
8 4
6 9

0
3
6

样例 1 解释

二叉树的一种建图方式如下，虽然输入的前序遍历和后序遍历无法确定唯一的二叉树，但是其层次遍历是唯一的，在得到的结果上也是完全一致的。

子任务

对于所有数据，保证节点个数和查询次数满足 $n,q\le 10^4$，输入的树各节点关键码互异，一定是代表一个二叉树结构。

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

提示

想一想在二叉树中，一个节点和它的祖先，在前序遍历以及后序遍历的相对位置是什么样的？

来源

清华 826 考研初试 2023 - 算法大题