P9056 [集训队互测 2022] 在路上

滥用本题评测者封号。 dottle bot。

**这是一道交互题，仅支持 C++ 提交**。 有一棵未知的树，**保证树的大小为奇数，你需要找到这棵树重心的编号**。 你可以进行询问，每次询问你可以询问三个点 $(x,y,z)$，若不存在一条简单路径同时经过三个点，则交互器会返回 $0$，否则若存在，那么交互器会返回三个点在路径上相对顺序中间的一个点。 令 $dis(a,b)$ 表示 $a,b$ 两点在树上最短路径经过的边数，你也可以理解为: 若 $dis(x,y)+dis(x,z)=dis(y,z)$，则交互器会返回 $x$。 否则若 $dis(y,x)+dis(y,z)=dis(x,z)$，交互器会返回 $y$。 否则若 $dis(z,x)+dis(z,y)=dis(x,y)$，交互器会返回 $z$。 否则交互器会返回 $0$。 在最终的测试中，每个测试点会包含 $T$ 组测试数据，和一个常数 $M$，表示你在所有测试数据中询问次数总和的上限，具体细则见 输入格式 以及 数据范围。 #### 实现细节 ~~你需要引用 `path.h` 头文件。~~ 本题中你只需要把 `path.h` 头文件的内容粘贴到程序开头即可，不要引用 `path.h` 头文件。 你需要实现下面的函数： ``` int centroid(int id,int N,int M); ``` 其中 $id$ 为当前子任务的编号，$N$ 为当前询问树的大小，$M$ 为当前测试点剩余的询问次数，函数的返回值为当前树的重心编号。 具体的，在第一次调用时 $M$ 为当前测试点的询问次数上限，每次调用结束之后 $M$ 会减去当前测试点使用的询问次数。 你可以调用下面的函数： ``` int ask(int x,int y,int z); ``` 表示你进行了一次询问，交互器会返回当前询问的答案，特别的，若询问次数已经超过了上限，交互器会返回 $-1$。 注意同一个测试点中 `centroid` 函数可能会被多次调用，请注意数组清空等情况。 **下发文件中有样例交互库，该交互库的实现与评测时的交互库几乎一致，如果对交互方式有不理解可以参照交互库的代码理解**。

样例评测库将读入如下格式的输入数据： 第一行三个整数 $id,T,M$，表示当前的子任务编号以及测试数据的数量，以及询问次数的上界。 对于每一组测试数据，第一行一个正整数 $n$，表示当前测试数据中树的大小。 之后一行 $n-1$ 个正整数，第 $i$ 个数表示 $i+1$ 在以 $1$ 为根意义下的父亲节点。 数据的答案将在交互库内部计算。

具体信息见交互库。

#### 数据范围  特殊性质 $A$：保证树的形态为一条链，即每个点的度数均不超过 $2$。 保证每个 Subtask 里的测试数据数量均不超过 $20$。**请仔细阅读每一档子任务及其限制**。 #### 时空限制 Subtask 5 时限为 3s。 Subtask 7,8 时限为 4s。 其余 Subtask 时限为 1s。 空间限制：512MB。 保证最终交互库的时间使用不超过 2s，空间使用不超过 64MB。 #### 下发文件 下发文件中有一个样例交互库，提供的交互头文件，一份示例代码，以及一个满足子任务 $4$ 性质的样例，选手也可以按照题目的输入格式构造其他样例。 另外也有一份洛谷样式的交互库。 保证下发的交互库和最终使用的交互库除反作弊之外没有区别，你可以使用这个交互库输出调试信息。