时间限制： 3.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$ 的通路。形象地说，就是 $x$ 沿着父节点向上走到 $x,y$ 两个点的最近公共祖先，再向下走到 $y$ 节点，你需要找到这条路上的所有节点（包含 $x,y$ 本身）。要求：

• 如果需要搜索，则需要从根节点出发，具体我们将在交互库做说明。
• 时间复杂度不能超过 $O(n)$。
• 不允许使用其他任何数据结构。
• 为简化题目，不要求通路上节点的输出顺序，你只需要正确输出所有节点即可。

Honor Code

我们在原则上不允许使用其他数据结构，或者搜索起点不为根节点。但是由于部署较为麻烦（懒得弄了，又不是什么正式比赛 QAQ），并没有封锁其他方式通过本题的可能性。

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

交互方式

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

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

你需要实现一个函数 void route(int x, int y)。给定树上的两个节点的编号，输出两个节点通路上的所有节点（包括这两个点）。

你可以调用以下函数：

int getLC(int u);
int getRC(int u);
void print(int u);

• getLC/getRC：输入一个节点编号，获取其左子节点/右子节点。当一个节点不存在左/右子节点时，返回 $0$。
• print：输出一个节点的编号，一个本该输出的节点输出多于 1 次不影响判题的正确性（也就是非通路节点不输出，通路节点输出至少 1 次即可）。

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

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

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

白盒交互库实例

具体请见附加文件区的 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$ 的右儿子。）。每次查询给出两个编号，输出一行一个整数为本次查询输出节点编号的异或和。

请注意，黑盒交互库不会只输出所有节点的异或和，因此请对所有节点都调用至少一次 print，而不是在中间计算节点编号的异或和结果。

6 3
1 2 2 1 5
3 4
3 3
2 6

5
3
0

样例 1 解释

样例给出的二叉树如图。

• $3$ 和 $4$ 号节点的通路为 $2,3,4$，因此 $2\oplus 3\oplus 4 = 5$。
• $3$ 和 $3$ 号节点的通路只有 $3$，因此直接输出 $3$。
• $2$ 和 $6$ 号节点的通路为 $2,1,5,6$，因此 $2\oplus 1\oplus 5\oplus 6=0$。

子任务

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

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

提示

如果找不出问题在哪，思考一下是否考虑了一些极端情况？

来源

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

改编作者：校验环