Background

dottle bot.

Description

This is an interactive problem, only C++, C++11, C++14, and C++17 are supported for submission.

There is an unknown tree. It is guaranteed that the size of the tree is odd. You need to find the index of the centroid of this tree.

You can perform queries. In each query, you can provide three nodes $(x, y, z)$. If there is no simple path that passes through all three nodes, the interactor will return $0$. Otherwise, if such a path exists, the interactor will return the node that lies in the middle of the relative order of the three nodes on that path.

Let $dis(a, b)$ denote the number of edges on the shortest path between nodes $a$ and $b$ in the tree. You can also understand it as follows:

• If $dis(x, y) + dis(x, z) = dis(y, z)$, the interactor returns $x$.
• Otherwise, if $dis(y, x) + dis(y, z) = dis(x, z)$, the interactor returns $y$.
• Otherwise, if $dis(z, x) + dis(z, y) = dis(x, y)$, the interactor returns $z$.
• Otherwise, the interactor returns $0$.

In the final tests, each test case will contain $T$ test data sets and a constant $M$, representing the upper limit on the total number of queries allowed across all test data sets. See the Input section and Constraints for details.

Implementation Details

You need to include the header file path.h.

You must implement the following function:

int centroid(int id,int N,int M);

• $id$ is the current subtask ID, $N$ is the size of the tree for the current query, and $M$ is the remaining number of queries allowed for the current test case. The function should return the index of the centroid of the current tree.
• Specifically, during the first call, $M$ is the initial query limit for the current test case. After each call, $M$ will be reduced by the number of queries used in that call.

You can call the following function:

int ask(int x,int y,int z);

• This performs a query, and the interactor returns the answer. Specifically, if the number of queries exceeds the limit, the interactor returns $-1$.
• Note that the centroid function may be called multiple times within the same test case; please ensure that arrays are cleared appropriately.

The provided files include a sample interactor. The implementation of this interactor is almost identical to the one used during evaluation. If you do not understand the interaction method, you can refer to the code of the interactor.

Evaluation

The sample interactor will read input data in the following format:

The first line contains three integers $id, T, M$, representing the current subtask ID, the number of test data sets, and the upper bound on the number of queries.

For each test data set, the first line contains a positive integer $n$, representing the size of the tree.

The next line contains $n-1$ positive integers, where the $i$-th number represents the parent of node $i+1$ when the tree is rooted at $1$.

The answer for the data will be calculated internally by the interactor.

Constraints

Special Property A: The tree is guaranteed to be a chain, meaning the degree of every node does not exceed $2$.

It is guaranteed that the number of test data sets in each subtask does not exceed $20$.

Please read the requirements for each subtask carefully.

Files

The provided files include a sample interactor, the required header file, a sample code, and a test case satisfying the properties of Subtask $4$. Participants can also construct other test cases according to the input format described in the problem.

It is guaranteed that the provided interactor is identical to the final evaluation interactor except for anti-cheating measures. You may use this interactor to output debugging information.

It is guaranteed that the final interactor will not exceed 2s in time and 64MB in memory usage.