P1055树的遍历（traverse）

【题目描述】

小 X 和小 R 来到了一座树形迷宫。为了确认每个出口都能够正常通行，小 R 需要从入口出发，到达全部出口后再返回入口。这个过程恰好相当于对整棵树进行一次遍历。

这座迷宫可以抽象成一棵拥有 $2^n$ 个叶结点的满二叉树，共有 $2^{n+1}-1$ 个结点，并按照从上到下、从左到右的顺序编号为 $1,2,\ldots,2^{n+1}-1$。

编号为 $1,2,\ldots,2^n-1$ 的结点是非叶结点。对于每个非叶结点 $u$，其左儿子编号为 $2u$，右儿子编号为 $2u+1$。编号为 $2^n,2^n+1,\ldots,2^{n+1}-1$ 的结点是叶结点。

每个非叶结点 $u$ 都有一名守卫。初始时，所有守卫均处于沉睡状态。在小 R 出发前，小 X 可以花费 $w_u$ 点预算将结点 $u$ 的守卫唤醒，总花费不能超过 $k$。

每个叶结点 $v$ 上写有一个符文 $q_v$。所有叶结点上的符文恰好构成 $1,2,\ldots,2^n$ 的一个排列。

小 R 从根结点 $1$ 出发，初始持有一个空序列 $p$，并按照下列规则完成巡查：

• 到达叶结点 $v$ 时，将符文 $q_v$ 加入序列 $p$ 的末尾，随后返回其父亲结点。
• 到达非叶结点 $u$ 时，若守卫已经被唤醒，小 R 必须先完整遍历左子树，再完整遍历右子树。
• 到达非叶结点 $u$ 时，若守卫仍处于沉睡状态，小 R 可以自行选择两个子树的遍历顺序。

当小 R 从根结点返回时，巡查结束。此时每个叶结点恰好被访问一次，得到的序列 $p$ 称为本次遍历的遍历序列。

小 R 能够知道哪些守卫已经被唤醒。小 X 希望最终的遍历序列字典序尽可能大，小 R 希望最终的遍历序列字典序尽可能小，双方都会采取最优策略。

对于两个长度相同的序列 $a,b$，若存在位置 $i$，使得 $a_i<b_i$，且对于所有 $1\leq j<i$ 都有 $a_j=b_j$，则称 $a$ 的字典序小于 $b$。

请你求出双方均采取最优策略时，小 R 遍历整棵树得到的遍历序列。

【输入格式】

从文件 $\textbf{\textit{traverse.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个整数 $n,k$，分别表示迷宫的规模与小 X 能够使用的预算上限。

第二行包含 $2^n-1$ 个非负整数 $w_1,w_2,\ldots,w_{2^n-1}$，其中 $w_u$ 表示将结点 $u$ 的守卫唤醒所需的花费。

第三行包含 $2^n$ 个正整数 $q_{2^n},q_{2^n+1},\ldots,q_{2^{n+1}-1}$，表示每个叶结点上的符文。

【输出格式】

输出到文件 $\textbf{\textit{traverse.out}}$ 中。

对于每组测试数据，输出一行 $2^n$ 个正整数，依次表示双方均采取最优策略时得到的遍历序列。

【样例 1 输入】

10 221 03142 151 16172 1

【样例 1 输出】

11 222 1

【说明/提示】

【样例 1 解释】

对于第一组测试数据，小 X 无法将根结点的守卫唤醒。小 R 会选择先访问符文为 $1$ 的叶结点，得到的遍历序列为 $(1,2)$。

对于第二组测试数据，小 X 可以将根结点的守卫唤醒，使小 R 必须先遍历左子树，得到的遍历序列为 $(2,1)$。

【样例 2】

见选手目录下的 $\textbf{\textit{traverse/traverse2.in}}$ 和 $\textbf{\textit{traverse/traverse2.ans}}$。

该组样例符合测试点 $1\sim3$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{traverse/traverse3.in}}$ 和 $\textbf{\textit{traverse/traverse3.ans}}$。

该组样例符合测试点 $4\sim6$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{traverse/traverse4.in}}$ 和 $\textbf{\textit{traverse/traverse4.ans}}$。

该组样例符合测试点 $7\sim19$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{traverse/traverse5.in}}$ 和 $\textbf{\textit{traverse/traverse5.ans}}$。

该组样例符合测试点 $20\sim25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq n\leq11$，单个测试点内所有测试数据满足 $\sum 4^n\leq5\times10^6$。

特殊性质 A：保证 $k=0$，且对于所有非叶结点 $u$，均有 $w_u\geq1$。

对于所有测试数据，保证：

• $0\leq c\leq25$，$1\leq T\leq10$。
• $0\leq k\leq10^{12}$。
• 对于所有 $1\leq u<2^n$，均有 $0\leq w_u\leq10^{12}$。
• $q_{2^n},q_{2^n+1},\ldots,q_{2^{n+1}-1}$ 构成 $1,2,\ldots,2^n$ 的一个排列。