Background

Do not use $\texttt{\#include "tree.h"}$.

You need to add the following content at the top of your file, and submit using C++17 or a higher language standard:

long long ask(int u, int d);

Problem Description

This is an interactive problem.

Given a positive integer $h$. Let $n = 2^h - 1$.

The interactive library hides a permutation $p$ of $1 \sim n$ and a sequence $f$ of length $n$, where each element is a positive integer not greater than $10^9$.

Now there is a full binary tree $G$ of depth $h$ with $n$ nodes, and the root is node $1$. Also, for any node $u$ satisfying $2 \le u \le n$, its parent node is $\left\lfloor\dfrac u 2\right\rfloor$.

In each query, you can choose two integers $u, d$ satisfying $1 \le u \le n$ and $1 \le d \le 10^9$. The interactive library will return the sum of $f_v$ over all nodes $v$ such that $\operatorname{dis}(p_u, v) = d$. In particular, if there is no such node $v$, the interactive library will return $0$.

Here, $\operatorname{dis}(u, v)$ is the number of edges on the simple path between node $u$ and node $v$. In particular, $\operatorname{dis}(u, u) = 0$.

You need to determine $\sum\limits_{i=1}^n f_i$ using no more than $2hn$ queries. The contestant’s score depends on the number of queries for a single testdata and, for any integer $u$, the maximum number of times you query the integer $\boldsymbol u$.

It is not guaranteed that the permutation $p$ and the sequence $f$ are fixed, i.e., the interactive library may be adaptive.

Implementation Details

You need to implement the following function:

long long solve(int subtask, int h);

• subtask indicates the test point index;
• $h$ is the height of the binary tree;
• This function should return the value of $\sum\limits_{i=1}^n f_i$;
• For each test point, this function may be called multiple times by the interactive library.

You can send a query to the interactive library by calling:

long long ask(int u, int d);

• $u$ is the center node of the query, and you must ensure $1 \leq u \leq n$;
• $d$ is the distance limit, and you must ensure $1 \leq d \leq 10^9$;
• This function will return the sum of $f$ values of nodes whose distance to node $p_u$ is exactly $d$.

The problem guarantees that within the allowed operation limit, the interactive library will run in no more than $1$ second; the memory usage of the interactive library is fixed and does not exceed $32 \text{ MiB}$.

Interaction Example

Suppose $h = 2$, $n = 3$, the hidden permutation is $p = [2, 1, 3]$, and the node weights are $f = [11, 45, 14]$. The following is a valid interaction:

Hint

Constraints

For all testdata, it is guaranteed that: $2 \leq h \leq 15$, number of test cases $1 \leq T \leq 1\,500$, and across all data the sum of $n$ satisfies $\sum n \leq 10^6$.

This problem has $2$ test points. The score and constraints for each test point are shown below.

Scoring

This problem will first be subject to the same restrictions as usual, e.g., a compilation error will cause the whole problem to score $0$ points; runtime errors, time limit exceeded, and memory limit exceeded will cause the corresponding test point to score $0$ points. Contestants can only access variables or data defined by themselves and those provided by the interactive library, and the corresponding memory space. Attempts to access other memory locations may cause compilation errors or runtime errors.

In each call to solve, the number of operations used by the program, $q$, must satisfy $q \leq 2hn$, otherwise it will receive $0$ points.

Based on the above conditions:

• In test point $1$, the program gets full marks if and only if the return value of solve is correct.

• In test point $2$, the score is computed as follows:

  • If the return value of solve is incorrect, the score is $0$.
  • If all return values of solve are correct, then each testdata in this test point is scored separately: let $q$ be the number of operations used, and for any integer $u$, let $x$ be the maximum number of times the integer $u$ is queried. Then the program gets $f(q) - g(x)$ points, where $f(q)$ is the maximum score among all satisfied conditions in the table below:

  Condition	Score
  $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$

  Here, $g(x)$ is computed as follows:

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

Translated by ChatGPT 5