因为最后的比较方式是字典序，可以明确肯定是贪心的先让第一个数尽量大，然后是第二个数尽量大，以此类推。
考虑到如果选出了第一个数，那么按照其 \(\text{dfs}\) 的方式，相当于是把根到这个树的链删掉了，变成了许多颗子树，然后在按照 \(\text{dfs}\) 遍历这几个子树的顺序依次在子树中类似的做。
进一步的，能发现一开始选出第一个数这个操作也是对于整颗树而言的，而这也可以算作树的一个子树。
于是可以发现只需要求出子树内一些信息即可。
考虑需要维护什么信息。
因为根据刚刚的步骤，能发现过程中只关注这个子树里面选的第一个数是什么。
就可以考虑树形 \(\text{DP}\)，设 \(f_{u, i}\) 为 \(u\) 这颗子树里选出的第一个数为 \(i\) 所需要的最小花费。
第二维是数是因为这是颗完全二叉树有个很好的性质是深度为 \(n\)，总状态数就是 \(O(2^nn)\) 的。
对于 \(f_{u, x}\) 就可以考虑从左儿子 \(ls\) 和右儿子 \(rs\) 来转移。
如果 \(x\in T_{ls}\)，那么有两种选择，一种是唤醒 \(u\) 的石像，还有一种是让 \(rs\) 走到的第一个数 \(> x\)，这样子为了更优肯定会走到 \(x\)，即 \(f_{u, x} = f_{ls, x} + \min\{a_u, \min\{f_{rs, y}\}\}(y\in T_{rs}, y > x)\)。
否则如果 \(x\in T_{rs}\)，那么就只会在 \(ls\) 走到的第一个数 \(> x\) 时才会走向 \(rs\)，即 \(f_{u, x} = f_{rs, x} + \min\{f_{ls, y}\}(y\in T_{ls}, y > x)\)。
用归并排序能做到 \(O(2^nn)\) 的复杂度。
考虑最后求答案。
假设当前子树能用的花费为 \(p\)，那么就需要求出 \(\max x(x\in T_u, f_{u, x}\le p)\)，相当于就是确定第一个树。
一种想法就是上文所提到的直接删掉子树到这个数的链去递归，但是能够发现这不能很好的处理不在这条链上被唤醒的石像的贡献。
考虑修补一下这个做法，确定了走到 \(x\) 这个点后就往下递归时逆推 \(f_{u, x}\) 的转移。
若 \(x\in T_{rs}\)，考虑转移时取到的 \(v = \min\{f_{ls, y}\}\)，相当于只需要至少给 \(ls\) 留下 \(v\) 的花费就可以走到 \(x\)，那么 \(rs\) 的花费相当于就是 \(p - v\)。
可能 \(rs\) 递归完属于 \(rs\) 的花费还有剩的，那就可以放进 \(ls\) 去做。
若 \(x\in T_{ls}\)，与上述差不多，令 \(v = \min\{a_u, \min\{f_{rs, y}\}\}\)，给 \(ls\) 花费为 \(p - v\) 然后递归下去，然后 \(v\) 加上 \(ls\) 剩的花费递归 \(rs\)。
需要注意的是递归 \(rs\) 如果 \(v\) 的 \(\min\) 取到的是 \(a_u\)，在 \(rs\) 中选出来的第一个走到的数 \(y\) 可能会 \(< x\)，如果发生这种情况那么就相当于是用的 \(a_u\) 的花费，减掉这部分花费即可。
时间复杂度就为状态数 \(O(2^nn)\)。
时间复杂度 \(O(2^nn)\)。
这份代码在转移时没有使用归并，时间复杂度 \(O(2^nn^2)\)。
代码
#include<bits/stdc++.h>
#define getc getchar_unlocked
template<typename Ty>
inline Ty read() {
char c = getc();
bool f = 0;
while (! isdigit(c)) f |= c == '-', c = getc();
Ty x = 0;
while (isdigit(c)) x = x * 10 + c - '0', c = getc();
return f ? -x : x;
}
using i64 = long long;
const i64 inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1 << 17;
int n; int N, M;
std::vector<i64> f[maxn];
std::vector<int> w[maxn];
i64 a[maxn];
std::vector<int> ans;
i64 dfs(int u, int v, int lw, i64 K) {
i64 co = 0;
if (! v) {
for (int i = 0; i < w[u].size(); i++) {
if (f[u][i] <= K) v = w[u][i];
}
if (v <= lw) co += a[u >> 1];
for (int i = 0; i < w[u].size(); i++)
if (f[u][i] <= K - co) v = w[u][i];
}
if (u >= N) {ans.push_back(a[u]); return co;}
int x = u << 1, y = u << 1 | 1;
int xi = std::lower_bound(w[x].begin(), w[x].end(), v) - w[x].begin();
int yi = std::lower_bound(w[y].begin(), w[y].end(), v) - w[y].begin();
if (xi < w[x].size() && w[x][xi] == v) {
i64 fy = yi == w[y].size() ? inf : f[y][yi];
co += dfs(x, v, 0, K - co - std::min(fy, a[u]));
co += dfs(y, 0, v, K - co);
} else {
co += dfs(y, v, 0, K - co - f[x][xi]);
co += dfs(x, 0, v, K - co);
}
return co;
}
inline void Main() {
n = read<int>(); i64 K = read<i64>();
N = 1 << n, M = 1 << n + 1;
for (int i = 1; i < M; i++) a[i] = read<i64>();
for (int u = M - 1; u; u--) {
f[u].clear(), w[u].clear();
if (u >= N) {
w[u].push_back(a[u]), f[u].push_back(0);
} else {
int x = u << 1, y = u << 1 | 1;
std::vector<int> W;
std::vector<i64> g;
for (int v : w[x]) W.push_back(v);
for (int v : w[y]) W.push_back(v);
std::sort(W.begin(), W.end());
for (int xi = 0, yi = 0, i = 0; i < W.size(); i++) {
if (xi < w[x].size() && w[x][xi] == W[i]) {
i64 v = f[x][xi] + std::min(yi == w[y].size() ? inf : f[y][yi], a[u]);
g.push_back(v);
xi++;
} else {
i64 v = f[y][yi] + (xi == w[x].size() ? inf : f[x][xi]);
g.push_back(v);
yi++;
}
}
for (int i = 0; i < W.size(); i++) {
int v = W[i]; i64 F = g[i];
if (F >= inf) continue;
while (! w[u].empty() && F <= f[u].back()) w[u].pop_back(), f[u].pop_back();
w[u].push_back(v), f[u].push_back(F);
}
}
}
ans.clear();
dfs(1, 0, 0, K);
for (int x : ans) printf("%d ", x);
puts("");
}
int main() {
freopen("maze.in", "r", stdin);
freopen("maze.out", "w", stdout);
int T = read<int>();
while (T--) Main();
return 0;
}