P11354 [eJOI 2023] Tree Search

本题对洛谷交互格式进行了适配，你可以在以下代码的基础上进行实现： ```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; } ```

**这是一道交互题。** 给定一棵 $N$ 个点的有根二叉树 $T$，保证根结点的编号为 $1$。 树上恰有一个未知的结点是特殊的，你需要找出这个结点。 你每次可以向交互库询问一棵子树中是否含有特殊结点，你可以询问至多 $35$ 次。 **【实现细节】** 你需要实现下列函数： ``int solve(int N, std::vector < int > p)`` - $N$：树的结点数量。 - $p$：长度为 $N-1$ 的数组，描述树的形态。第 $i$ 个元素 $p_i$ 满足 $1\leq p_i\leq i+1$，代表编号为 $i+2$ 的结点的父亲编号。 - $p$ 中的元素两两不同。 - 你需要返回特殊结点的编号。 - 这个函数只会被调用恰好一次。 你可以调用以下函数： ``int ask(int x)`` - $x$：询问的子树根结点编号。 - 你需要保证 $1\leq x\leq N$。 - 如果子树包含特殊结点，返回值为 $1$，否则为 $0$。

**以下为下发 grader 的输入格式，你不应该从标准输入中读入任何信息。** 第一行输入一个整数 $N$。 第二行输入 $N-1$ 个整数 $p_i$。 接下来对于每个询问，输入一个整数代表询问的返回值。

**以下为下发 grader 的输出格式，你不应该向标准输出中打印任何信息。** 对于每个询问，输出一行 ``? x``，其中 $x$ 为询问的结点。 最后输出一行 ``! x``，其中 $x$ 为猜测的结点编号。

**【数据范围】** **本题采用捆绑测试。** - 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）：无特殊限制。 对于 $100\%$ 的数据，保证 $1\leq N\leq 10^5$。