这是一道交互题。

题目描述

给定一个正整数 \(h\)，我们令 \(n = 2^h - 1\)。

交互库隐藏了一个 \(1 \sim n\) 的排列 \(p\) 和一个长度为 \(n\) 且每个元素均为不大于 \(10^9\) 的**正整数**的序列 \(f\)，你需要通过不超过 \((2n + 3)\) 次询问求出 \(\sum\limits_{i=1}^n f_i\) 的值。

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

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

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

你需要在不超过 \(2hn\) 次询问内求出 \(\sum\limits_{i=1}^n f_i\) 的值。选手得分与单组测试数据询问次数以及对于任意整数 \(u\)，对整数 \(u\) 进行询问的次数最大值有关。

不保证排列 \(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\) 秒；交互库使用的内存大小固定，且不超过 \(32 ~\text{MiB}\)。

测试程序方式

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

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

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

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

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

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

• 可执行文件将从**标准输入**读入以下格式的数据：

  • 输入的第一行包含两个整数 \(c,T\)，表示测试点编号和数据组数；
  • 对于每组数据包含三行：
  • 第一行包含一个正整数 \(h\)；
  • 第二行包含 \(n = 2^h - 1\) 个数组空格隔开，表示题目描述中的隐藏排列；
  • 第三行包含 \(n = 2^h - 1\) 个数组空格隔开，表示 \(f\) 序列的值。

• 对于每组数据，交互库将调用一次函数 tree 进行测试，测试全部完成后，交互库将会向标准错误流输出以下信息：

  • 第一行包含你的得分信息；
  • 第二行包含交互库关于测试结果给出的描述；

• 如果开启了调试模式，交互库会向标准错误流打印每一次询问的详细信息。**请确保开启调试模式时输入的测试数据较小从而避免意外产生。**

交互示例

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

选手程序	交互库	说明
	调用 tree(1, 2)	开始测试
调用 ask(1, 1)	返回 \(11\)	距离 \(p_1 = 2\) 正好为 \(1\) 的点只有结点 \(1\)，权值总和为 \(11\)
调用 ask(2, 1)	返回 \(59\)	距离 \(p_1 = 1\) 正好为 \(1\) 的点有结点 \(2\), \(3\)，权值总和为 \(45 + 14 = 59\)
调用 ask(3, 1)	返回 \(11\)	距离 \(p_1 = 3\) 正好为 \(1\) 的点只有结点 \(1\)，权值总和为 \(11\)
运行结束并返回 \(70\)	向屏幕打印交互结果	交互结果，结果正确

下发文件说明

在本试题目录下：

1. grader.cpp 是提供的交互库参考实现。
2. tree.h 是头文件，选手不用关心具体内容。
3. template_tree.cpp 是提供的示例代码，选手可在此代码的基础上实现。

选手注意对所有下发文件做好备份。最终评测时只测试本试题目录下的 tree.cpp，对该程序以外文件的修改不会影响评测结果。

数据范围

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

本题共 \(2\) 个测试点，每个测试点的分值和数据范围见下表。

测试点编号	分值	特殊性质
\(1\)	\(10\)	保证 \(h = 2\)，数据组数 \(T = 100\)
\(2\)	\(90\)	无特殊限制

评分方式

注意：

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

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

在每次 solve 函数调用中，程序使用的操作次数 \(q\) 需要满足 \(q \leq 2hn\) 的限制，否则将会获得 \(0\) 分。

在上述条件基础上：

• 在测试点 \(1\) 中，程序得到满分当且仅当 solve 函数返回的答案正确；

• 在测试点 \(2\) 中，程序得到的分数将按照以下方式计算：

  • 若 solve 函数返回的答案不正确，则获得 \(0\) 分；
  • 若 solve 函数返回的答案均正确，则对于该测试点的所有测试数据分别计分：设程序使用的操作次数为 \(q\)，对于任意整数 \(u\)，对整数 \(u\) 进行询问的次数最大值为 \(x\)，则程序将获得 \(f(q) - g(x)\) 分，其中 \(f(q)\) 的计算方式为 \(q\) 在下表中所有满足的条件中，对应分值的最大值：

条件	分值
\(q \leq 2n + 3\)	\(90\)
\(q \leq 2n + 4\)	\(82\)
\(q \leq 2n + 5\)	\(76\)
\(q \leq 2n + h + 2\)	\(72\)
\(q \leq 2n + h + 4\)	\(69\)
\(q \leq 2n + 2h + 2\)	\(66\)
\(q \leq 2n + 2h + 4\)	\(63\)
\(q \leq 3n + 3\)	\(59\)
\(q \leq 3n + 5\)	\(56\)
\(q \leq 3n + h + 4\)	\(53\)
\(q \leq 3n + 2h + 4\)	\(50\)
\(q \leq 4n + 3\)	\(43\)
\(q \leq 4n + 5\)	\(40\)
\(q \leq 4n + h + 4\)	\(37\)
\(q \leq 4n + 2h + 4\)	\(34\)
\(q \leq 2hn\)	\(30\)

其中 \(g(x)\) 的计算方式如下表所示：

\(x\)	\(g(x)\)
\(\leq 4\)	\(0\)
\(= 5\)	\(10\)
\(= 6\)	\(15\)
\(> 6\)	\(20\)

tree.zip