Background

This problem has been adapted to Luogu’s interactive format. You can implement your solution based on the following code:

#include<bits/stdc++.h>
using namespace std;
extern "C" bool ask(int x);
extern "C" int solve(int n,vector<int> p)
{
  	assert(ask(1)==1);
	return 20080520;
}

Problem Description

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$.

Input Format

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.

Output Format

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.

5
1 1 2 4

1

0
 

 

? 4

? 5

! 4

Hint

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