我称呼这是一道绝世好签到题，看本文标题就知道，简单、二分、贪心、递归，签到属性拉满！
题意要求满二叉树上最大化最小叶子点权字典序，可以使用 w
x
个“贝”强制某个非叶子节点往左走。
这里的叶子节点点权是一个排列，不然可能会变得复杂一些。
考虑先求出第一个节点的点权，可以二分点权 ≥mid，设 dp(x) 表示走到节点 x 后，使得第一个叶子点权 ≥mid 的最少要用多少个“贝”。
显然 dp(x)=dp(2x)+min{w
x
,dp(2x+1)}，边界叶子节点 dp
x
=[q
x
<mid]×inf。
于是我们得知了第一个要走的数是什么，于是可以得出刚开始会往那一棵子树走。
如果是往左子树走，这是我们需要 min{w
x
,dp(2x+1)} 的代价来强制往左走或者使得右儿子优于左儿子，否则需要 dp(2x) 的代价来使得左儿子优于右儿子（对方会走更劣的一边），我们称此为强制花费。
当然这里的贪心策略就是根据字典序的性质，我们应当在不浪费的前提下尽量早地花钱。
定义 pair<ll,vector<int> >sol(int x,ll up) 表示走到节点 x，可用 up 个“贝”，返回最优策略下的花费和答案。
然后就可以递归求解了，每次先二分得出先前往的子树，它可以使用的 up 为当前的 up 减去强制花费，然后递归另一边子树。
当然对于 w
x
是否使用，如果递归完左子树时剩余费用达到了 dp(2x+1)，就不需要使用 w
x
了，因为右儿子存在优于左儿子的策略，否则就是唯一使用 w
x
的场景。
需要排序得出每个子树内存在的需要二分的值，虽然可以归并，但是我全部都使用了暴力 sort，因为实在是太快了！
时间复杂度 O(n
2
2
n
)，但是跑得很快：
#include<bits/stdc++.h>
// bool stc;
#define all(x) x.begin(),x.end()
#define cln cerr<<"Line: "<<LINE<<" "
using namespace std;
const int N=(1<<20)+100;
using ll=long long;
int T,n,m,a[N],b[N];
ll K,w[N],f[N],mst;
using vt=vector<int>;
using D1=pair<ll,vt>;
#define ls x<<1
#define rs x<<1|1
vt h[N];
vt mg(vt a,vt b){
for(auto &p:b)a.push_back(p);
return a;
}
void dp(int x){
if(x>>n)f[x]=a[x]<mst?K+1:0;
else{
dp(ls),dp(rs);
f[x]=f[ls]+min(f[rs],w[x]);
}
}
int fd(vt &a,int v){
auto it=lower_bound(all(a),v);
return (it!=a.end())&&(*it==v);
}
D1 sol(int x,ll up){
if(x>>n)return D1(0,{a[x]});
int l=1,r=h[x].size()-1,md,k=0;
while(l<=r){
md=l+r>>1;
mst=h[x][md],dp(x);
if(f[x]<=up)k=md,l=md+1;
else r=md-1;
}mst=h[x][k],dp(x);
// printf("x:%d k:%d up:%lld f:%lld\n",x,k,up,f[x]);
// for(int p:h[x])printf("%d ",p);puts("");
if(fd(h[ls],h[x][k])){
auto at=sol(ls,up-min(w[x],f[rs]));
up-=at.first;
if(up>=f[rs]){
auto bt=sol(rs,up);
return D1(at.first+bt.first,mg(at.second,bt.second));
}else{
up-=w[x];
auto bt=sol(rs,up);
return D1(at.first+bt.first+w[x],mg(at.second,bt.second));
}
}else{//printf("x:%d\n",x);
auto at=sol(rs,up-f[ls]);
up-=at.first;auto bt=sol(ls,up);
return D1(at.first+bt.first,mg(at.second,bt.second));
}
}
// bool edc;
int main(){
// double meg=fabs(&edc-&stc)/1048576,lim=300;
// cerr<<meg<<endl,assert(meg<lim);
ios::sync_with_stdio(false),cin.tie(0);
freopen("maze.in","r",stdin);
freopen("maze.out","w",stdout);
int i,j,k,l,r,x,y,z;
for(cin>>T;T--;){
cin>>n>>K;
for(x=1;x<(1<<n);++x)cin>>w[x];
for(x=(1<<n);x<(1<<n+1);++x){
cin>>a[x];
for(k=x;k;k>>=1)h[k].push_back(a[x]);
}
for(x=1;x<(1<<n);++x)sort(all(h[x]));
auto ans=sol(1,K).second;
for(int p:ans)printf("%d ",p);putchar('\n');
for(x=1;x<(1<<n+1);++x)h[x].clear();
}
return 0;
}
