P11354 [eJOI 2023] Tree Search

This problem has been adapted to Luogu’s interactive format. You can implement your solution based on the following code: ```cpp #include using namespace std; extern "C" bool ask(int x); extern "C" int solve(int n,vector p) { assert(ask(1)==1); return 20080520; } ```

**This is an interactive problem.** You are given a rooted binary tree $T$ with $N$ nodes, and the root is guaranteed to have index $1$. Exactly one unknown node in the tree is special, and you need to find this node. Each time, you may ask the interactive library whether a subtree contains the special node. You may ask at most $35$ times. **Implementation Details** You need to implement the following function: ``int solve(int N, std::vector < int > p)`` - $N$: the number of nodes in the tree. - $p$: an array of length $N-1$ describing the shape of the tree. The $i$-th element $p_i$ satisfies $1\leq p_i\leq i+1$ and represents the parent index of node $i+2$. - All elements in $p$ are pairwise distinct. - You need to return the index of the special node. - This function will be called exactly once. You may call the following function: ``int ask(int x)`` - $x$: the index of the root of the subtree being queried. - You must ensure $1\leq x\leq N$. - If the subtree contains the special node, it returns $1$; otherwise it returns $0$.

**The following is the input format of the provided grader. You should not read any information from standard input.** The first line contains an integer $N$. The second line contains $N-1$ integers $p_i$. Then, for each query, an integer is given representing the return value of the query.

**The following is the output format of the provided grader. You should not print any information to standard output.** For each query, output one line ``? x``, where $x$ is the node being queried. Finally, output one line ``! x``, where $x$ is the index of the guessed node.

**Constraints** **This problem uses bundled testdata.** - Subtask 1 (20 pts): $N\leq 35$. - Subtask 2 (30 pts): $p_i=i+1$. - Subtask 3 (15 pts): $p_i=\frac{i}{2}+1$. - Subtask 4 (35 pts): no special constraints. For $100\%$ of the testdata, it is guaranteed that $1\leq N\leq 10^5$. Translated by ChatGPT 5