Background

Abusing the judge of this problem will result in your account being banned.

dottle bot。

Problem Description

This is an interactive problem and only supports C++ submissions.

There is an unknown tree. It is guaranteed that the size of the tree is odd, and you need to find the label (index) of the centroid of this tree.

You can make queries. In each query, you may query three nodes $(x,y,z)$. If there does not exist a 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 is in the middle among the three nodes in their relative order 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:

If $dis(x,y)+dis(x,z)=dis(y,z)$, then the interactor returns $x$.

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

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

Otherwise, the interactor returns $0$.

In the final test, each test point contains $T$ groups of testdata and a constant $M$, which indicates the upper bound on the total number of queries across all testdata. See Input Format and Constraints for the detailed rules.

Implementation Details

You need to include the header file path.h. In this problem, you only need to paste the contents of the path.h header file at the beginning of your program. Do not include the path.h header file.

You need to implement the following function:

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

Here, $id$ is the index of the current subtask, $N$ is the size of the current queried tree, and $M$ is the remaining number of queries for the current test point. The return value of the function should be the label (index) of the centroid of the current tree.

Specifically, in the first call, $M$ is the query limit for the current test point. After each call ends, $M$ will be reduced by the number of queries used in the current test point.

You may call the following function:

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

This means you perform one query, and the interactor returns the answer to the current query. In particular, if the number of queries has exceeded the upper bound, the interactor will return $-1$.

Note that within the same test point, the centroid function may be called multiple times. Please be careful about clearing arrays and similar issues.

The provided files contain a sample interactive library. Its implementation is almost the same as the interactive library used in judging. If you do not understand the interaction method, you can refer to the code of the interactive library to understand it.

Input Format

The sample judging library will read input in the following format:

The first line contains three integers $id,T,M$, representing the current subtask index, the number of testdata, and the upper bound on the number of queries.

For each group of testdata, the first line contains a positive integer $n$, representing the size of the tree in the current testdata.

Then there is a line with $n-1$ positive integers. The $i$-th number indicates the parent of $i+1$ under the interpretation that the tree is rooted at $1$.

The answer for the data will be computed inside the interactive library.

Output Format

See the interactive library for details.

Hint

Constraints

Special property $A$: The shape of the tree is guaranteed to be a chain, i.e., the degree of each node is at most $2$.

It is guaranteed that the number of testdata in each Subtask does not exceed $20$. Please read carefully each subtask and its limits.

Time and Memory Limits

The time limit for Subtask 5 is 3 s.

The time limit for Subtask 7 and 8 is 4 s.

The time limit for the other Subtasks is 1 s.

Memory limit: 512 MB.

It is guaranteed that the final interactive library uses no more than 2 s of time and no more than 64 MB of memory.

Provided Files

The provided files include a sample interactive library, the provided interactive header file, a piece of sample code, and a sample that satisfies the property of subtask $4$. Contestants may also construct other samples according to the input format of the problem.

In addition, there is also a Luogu-style interactive library.

It is guaranteed that, except for anti-cheating, the provided interactive library is the same as the interactive library used in the final judging. You may use this library to output debugging information.

Translated by ChatGPT 5