English Statement

这是一道交互题。

在解决 Ad-hoc Master 后，你想要解决下面的问题。

给定一个正整数 $h$。我们令 $n=2^h-1$。

交互库隐藏了一个 $1 \sim n$ 的排列 $p$ 和一个长度为 $n$ 且每个元素均为不大于 $10^9$ 的正整数的序列 $f$。

现在有一棵深度为 $h$，包含 $n$ 个结点的满二叉树 $G$，根结点为 $1$ 号结点。同时，对于任意一个满足 $2 \le u \le n$ 的结点 $u$，都满足其父亲结点为结点 $\left\lfloor\dfrac u 2\right\rfloor$。

每次询问，你可以选择两个满足 $1 \le u \le n$ 和 $1 \le d \le 10^9$ 的整数 $u,d$，交互库会返回所有满足 $\operatorname{dis}(p_u,v)=d$ 的结点 $v$ 所对应的 $f_v$ 之和。特别的，若没有满足条件的结点 $v$，则交互库会返回 $0$。

其中，$\operatorname{dis}(u,v)$ 的值等于结点 $u$ 和结点 $v$ 之间的简单路径所包含的边的数量。特别的，$\operatorname{dis}(u,u)=0$。

你需要在不超过 $5n$ 次询问内求出 $\sum\limits_{i=1}^n f_i$ 的值；并且，对于每个整数 $\boldsymbol u$，你最多对其进行 $\boldsymbol 5$ 次询问。整数 $d$ 没有其他限制。选手得分与单组测试数据询问次数有关。

不保证排列 $p$ 和序列 $f$ 是固定的，即交互库可能是自适应的。

实现细节

选手不需要，也不应该实现 main 函数。

选手应确保提交的程序包含头文件 tree.h，可在程序开头加入以下代码实现：

#include "tree.h"

选手需要实现以下函数：

long long solve(int subtask, int h);

• subtask 表示子任务编号；
• $h$ 表示二叉树的高度；
• 该函数需要返回 $\sum\limits_{i=1}^n f_i$ 的值；
• 对于每个测试点，该函数可能会被交互库调用多次。

选手可以通过调用以下函数向交互库发送一次询问：

long long ask(int u, int d);

• $u$ 表示询问的中心结点，你需要保证 $1 \leq u \leq n$；
• $d$ 表示询问的距离限制，你需要保证 $1 \leq d \leq 10^9$；
• 该函数将返回到点 $p_u$ 正好为 $d$ 的结点的 $f$ 值之和。

题目保证在规定的操作次数限制下，交互库运行所需的时间不超过 $1$ 秒；交互库使用的内存大小固定，且不超过 $128 \text{ MiB}$。

测试程序方式

试题目录下的 grader.cpp 是提供的交互库参考实现，最终测试所用的交互库与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。

选手可以在本题目录下使用如下命令编译得到可执行程序：

g++ grader.cpp tree.cpp -o tree -O2 -std=c++14

你也可以添加 -DDEBUG 选项来开启调试模式：

g++ grader.cpp tree.cpp -o tree -O2 -std=c++14 -DDEBUG

对于编译得到的可执行程序：

• 可执行文件将从标准输入读入以下格式的数据：
  • 输入的第一行包含两个整数 $subtask, T$，表示子任务编号和数据组数；
  • 对于每组数据包含三行：
    • 第一行包含一个正整数 $h$；
    • 第二行包含 $n = 2^h - 1$ 个数用空格隔开，表示题目描述中的隐藏排列；
    • 第三行包含 $n = 2^h - 1$ 个数用空格隔开，表示 $f$ 序列的值。
• 对于每组数据，交互库将调用一次函数 tree 进行测试，测试全部完成后，交互库将会向标准错误流输出以下信息：
  • 第一行包含你的得分信息；
  • 第二行包含交互库关于测试结果给出的描述；
• 如果开启了调试模式，交互库会向标准错误流打印每一次询问的详细信息。请确保开启调试模式时输入的测试数据较小从而避免意外产生。

交互示例

假设 $h = 2$，$n = 3$，隐藏排列 $p = [2, 1, 3]$，结点权值 $f = [11, 45, 14]$，下面是一个合法的交互过程：

下发文件说明

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. tree.h 是头文件，选手不用关心具体内容。
3. template_tree.cpp 是提供的示例代码，选手可在此代码的基础上实现。
4. tree1.in 是“交互示例”对应的样例交互器输入。
5. tree2.in、tree3.in、tree4.in 分别是满足子任务 $2 \sim 4$ 的一组样例交互器输入。

数据范围

对于所有测试数据保证：$2 \leq h \leq 18$，数据组数 $1 \leq T \leq 10^5$，所有数据中 $n$ 的和 $\sum n$ 不超过 $10^6$。

本题共 $4$ 个子任务，每个子任务的分值和数据范围见下表。

一个子任务的得分为该子任务中所有测试点的得分最小值，单个测试点得分计算方式见“评分方式”。

评分方式

注意：

• 选手不应通过非法方式获取交互库的内部信息，如试图直接读取排列 $p$ 或者序列 $f$ 等，或直接与标准输入、输出流进行交互。此类行为将被视为作弊；
• 最终的评测交互库与样例交互库的实现不同，且可能是适应性的：在不与 ask 此前返回的结果相矛盾的前提下，最终的评测交互库可能会动态调整隐藏排列 $p$ 和结点的权值。

本题首先会受到和传统相同的限制，例如编译错误会导致整道题目得 $0$ 分，运行时错误、超过时间限制、超过空间限制都会导致相应测试点得 $0$ 分。选手只能在程序中访问自己定义的和交互库给出的变量或数据，及其相应的内存空间。尝试访问其他位置空间将可能导致编译错误或运行错误。

在每次 solve 函数调用中，程序使用的操作次数 $q$ 需要满足 $q \leq 5n$ 的限制，对同一个 $u$ 的操作次数至多为 $5$ 次，否则将会获得 $0$ 分。

在上述条件基础上，程序得到的分数将按照以下方式计算：

• 若 solve 函数返回的答案不正确，则获得 $0$ 分；
• 若 solve 函数返回的答案均正确，则对于该子任务的所有测试数据分别计分，取得分的最小值：设程序使用的操作次数为 $q$，该子任务的分值为 $x$，则程序将获得 $x \cdot f(q)$ 分，其中 $f(q)$ 的计算方式为 $q$ 在下表中所有满足的条件中，对应得分比例的最大值：

时间限制： $\texttt{3s}$（交互库至多使用 $\texttt{1s}$）

空间限制： $\texttt{1024MB}$（交互库至多使用 $\texttt{128MB}$）