Universal Cup题目背景
dottle bot。
题目描述
这是一道交互题，仅支持 C++,C++11,C++14,C++17 提交。
有一棵未知的树，保证树的大小为奇数，你需要找到这棵树重心的编号。
你可以进行询问，每次询问你可以询问三个点 $(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 头文件。
你需要实现下面的函数：
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$ 为根意义下的父亲节点。
数据的答案将在交互库内部计算。
数据范围
| 子任务编号 | 子任务分数 | $t$ | $n$ | $M$ | 特殊性质 |
|---|---|---|---|---|---|
| $1$ | $2$ | $=100$ | $=3$ | $=100$ | 无 |
| $2$ | $8$ | $=10$ | $=999$ | $=10^7$ | |
| $3$ | $12$ | $=100$ | A | ||
| $4$ | $17$ | 无 | |||
| $5$ | $18$ | $=49\,999$ | $=2.5 \times 10^7$ | A | |
| $6$ | $12$ | $=9\,999$ | $=4\times 10^7$ | 无 | |
| $7$ | $19$ | $=50$ | $=29\,999$ | ||
| $8$ | $12$ | $=100$ | $=5\times 10^7$ |
特殊性质 A：保证树的形态为一条链，即每个点的度数均不超过 $2$。
保证每个 Subtask 里的测试数据数量均不超过 $20$。
请仔细阅读每一档子任务及其限制。
下发文件
下发文件中有一个样例交互库，提供的交互头文件，一份示例代码，以及一个满足子任务 $4$ 性质的样例，选手也可以按照题目的输入格式构造其他样例。
保证下发的交互库和最终使用的交互库除反作弊之外没有区别，你可以使用这个交互库输出调试信息。
保证最终交互库的时间使用不超过 2s，空间使用不超过 64MB。