注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

请在提交源代码前添加 #include "stub.h"。

题目描述

本题译自 eJOI2023 Problem A. Tree Search

给定一个由 $N$ 个顶点组成的有根二叉树。顶点从 $1$ 到 $N$ 编号，根是顶点 $1$。其他每个顶点在树中都有一个父节点。这是一个二叉树，即每个顶点最多可以是其他两个顶点的父节点。

其中一个顶点是特殊的。你正在试图寻找这个节点。你可以询问以下问题：「特殊顶点是否在顶点 $x$ 的子树中？」当且仅当从 $y$ 到 $1$ 的最短路径经过顶点 $x$ 时，节点 $y$ 才在顶点 $x$ 的子树中。注意，顶点 $x$ 也在自己的子树中。

你最多询问 $35$ 次。然后你应该给出你的答案。

实现细节

你应该实现以下函数：

int solve(int N, std::vector<int> p)

• $N$：顶点的数量
• $p$ 包含恰好 $N - 1$ 个元素，描述了一棵树：每个 $0 \leq i \leq N - 2$，顶点 $p_i$（其中 $1 \leq p_i \leq i + 1$）是顶点 $i + 2$ 的父节点。
• $p$ 中的元素不会出现超过两次
• 这个函数应该返回特殊顶点的编号
• 这个函数只被调用一次

你可以调用以下函数：

int ask(int x)

• $x$：顶点的编号
• $1 \leq x \leq N$
• 如果特殊顶点在 $x$ 的子树中，则返回 $1$，否则返回 $0$

样例

考虑以下调用：

solve(5, [1, 1, 2, 4])

树由边 $(1,2),(1,3),(2,4),(4,5)$ 组成。

你的程序调用了

ask(4)

返回了 $1$。然后你的程序调用了

ask(5)

返回了 $0$。

你的程序得出结论，顶点 $4$ 是特殊的，并返回了 $4$。

评测程序示例

评测程序示例按以下格式读取输入：

• 第 $1$ 行：$N$
• 第 $2$ 行：$p_0, p_1, \ldots , p_{N - 2}$

评测程序示例以以下格式输出每个问题：

• 第 $1$ 行：$?\ x$

评测程序示例按以下格式读取每个答案：

• 第 $1$ 行：$!\ y$

数据范围与提示

对于所有输入数据，满足：

• $2 \leq N \leq 10^5$

详细子任务附加限制及分值如下表所示。

子任务	附加限制	分值
$1$	$N\leq 35$	$20$
$2$	$p_i = i + 1\ (0 \leq i \leq N - 2)$	$30$
$3$	$p_i = \lfloor i/2 \rfloor + 1\ (0 \leq i \leq N - 2)$	$15$
$4$	无附加限制	$35$