duyi 的切题树（tree）

题目类型

函数式交互题。

你需要使用下发的头文件 tree.h，并实现指定函数。评测过程中不使用传统的标准输入、标准输出交互方式。

题目描述

duyi 有一棵“切题树”。这棵树是一棵高度为 $n$ 的满二叉树，根节点的高度为 $1$，因此整棵树共有

$$2^n-1$$

个节点。

duyi 有 $2^n-1$ 道要切的题。为了便于辨认，这些题被编号为

$$1,2,\ldots,2^n-1.$$

每天，duyi 会使用随机数生成器生成一个排列，并按照该排列的顺序，将所有题目依次放入树中。保证每个节点恰好放置一道题。随后，duyi 会切掉位于根节点上的题目。

你获得了接下来 $10000$ 天的随机顺序。对于每一天，你需要找出位于根节点上的题目编号。

为了确定答案，每一天你最多可以进行 $S$ 次询问。每次询问指定一道题的编号，系统会返回这道题所在节点的所有相邻节点上放置的题目编号。

交互接口

本题不使用传统文件输入输出。

你需要在程序开头包含头文件：

#include "tree.h"

头文件中提供如下询问函数：

std::vector<int> query(int x);

调用 query(x) 后，评测库会返回一个 std::vector<int>，其中包含编号为 $x$ 的题目在树中的所有相邻节点上放置的题目编号。

返回的所有编号均位于区间

$$[1,2^n-1]$$

内，并且互不相同。

每次调用 query 时，你传入的参数也必须满足

$$1\le x\le 2^n-1.$$

否则该次评测将被判为 Wrong Answer。

你需要实现如下函数：

int solve(int n);

其中，参数 $n$ 表示满二叉树的高度。函数返回值应为当天位于根节点上的题目编号。

对于每个子任务，可能包含若干个测试点。对于每个测试点，评测库会调用 solve 函数 $10000$ 次。只有全部调用均正确，该测试点才能获得满分。

注意：如果程序中使用了自定义全局变量，需要在每次调用 solve 时自行清空或重新初始化。

示例程序

下面是一份合法的程序，但它无法获得有效分数：

#include <bits/stdc++.h>
#include "tree.h"

using namespace std;

int solve(int n) {
    vector<int> v = query(1);
    return v.back();
}

本地测试

下发文件中包含 tree.h。按照上述接口完成程序后，可以直接进行本地测试。

本地测试程序的输入包含三个值：

n S seed

其中：

• $n$ 表示树的高度；
• $S$ 表示每天最多允许进行的询问次数；
• seed 表示随机种子，可以是 unsigned 类型范围内的任意整数。

本题没有传统输出。程序不能向标准输出 stdout 输出任何内容，否则可能被判为 $0$ 分。

数据范围与约定

记 $S$ 为每一天允许进行的最大询问次数。

对于所有数据：

$$1\le n\le 12.$$

子任务	分值	限制
1	$10$	$S=4095$
2	$15$	$S=100$
3	$5$	$n=3,\ S=3$
4	$10$	$n=4,\ S=5$
5		$S=60$
6	$20$	$S=51$
7	$30$	$S=50$

@原题面

@下发文件