自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 22:55:52，当前版本为作者最后更新于2024-03-07 21:01:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑 Bob 只选一个叶子时怎么做。

那么 Alice 每选择一个点，就相当于把右子树删掉，最后要使剩下数中的最小值最大。

考虑 $DP$ 记 $f_{u,j}$ 表示使 $u$ 子树内最小值大于等于 $j$ 的最小代价。

转移有 $f_{u,j}=f_{ls_u,j}+\min(f_{rs_u,j},w_u)$。

直接记录状态是 $O(4^n)$，因为树是满二叉树，可以对 $j$ 这一维离散化，这样状态就是 $O(n 2^n)$ 的。

转移可以用归并排序做到 $O(n 2^n)$。

求出 $f$ 后，找到最大的 $j$ 使得 $f_{1,j}\le K$，这就是 Bob 选的叶子。

考虑如何利用 $f$ 求出所有答案，直接模拟 Bob 在树上行走。

设计函数 $\operatorname{dfs}(u,K)$ 表示 Bob 走到了 $u$ 节点，Alice 还有 $K$ 的魔力值，函数返回 Alice 在 $u$ 子树内花费的魔力值。

一样找到最大的 $j$ 使得 $f_{u,j}\le K$，则 Bob 下一个叶子会走向 $j$。

如果 $j$ 在右子树，说明 Alice 一定不会选 $u$，那么依次调用 $g=\operatorname{dfs}(rs_u,K-f_{ls_u,j})，\operatorname{dfs}(ls_u,K-g)$ 即可。

如果 $j$ 在左子树，先调用 $g=\operatorname{dfs}(ls_u,K-\min(w_u,f_{rs_u,j}))$。

这时候我们要考虑 Alice 是否选择 $w_u$，请注意，并不是 $w_u\le f_{rs_u,j}$ 就会选择 $w_u$。

因为我们选择了 $w_u$ 会使得 Alice 在右子树的选择更少，只有在我们不选 $w_u$ 的情况下，左子树答案会改变才会选。

具体的，只有 $g\gt K-f_{rs_u,j}$ 时，我们才会选 $w_u$。

判断出是否选 $w_u$ 后，剩下的过程和 $j$ 在右子树的情况类似。

时间复杂度 $O(n2^n)$。

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<17)+5;
const ll inf=1e13;
int T,n,tn,a[N],rv[N],b[N],cb,c[18][N];
ll w[N],m,f[18][N],fl[18][N],fr[18][N];
bool vw[18][N];
#define ls(x) ((x)<<1)
#define rs(x) ((x)<<1|1)
void dfs(int x,int l,int r,int d){
	if(x>=tn){
		f[d][l]=0,c[d][l]=a[x];
		return;
	}
	int mid=l+r>>1;
	dfs(ls(x),l,mid,d+1),dfs(rs(x),mid+1,r,d+1);
	int i=l,j=mid+1,k=l;
	ll vl=0,vr=0;
	while(i<=mid&&j<=r){
		if(c[d+1][i]<c[d+1][j]){
			c[d][k]=c[d+1][i];
			vl=f[d+1][i];
			vr=f[d+1][j];
			++i;
		}else{
			c[d][k]=c[d+1][j];
			vr=f[d+1][j];
			vl=f[d+1][i];
			++j;
		}
		fl[d][k]=vl,fr[d][k]=vr;
		if(w[x]<vr)vw[d][k]=true;
		else vw[d][k]=false;
		f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
		++k;
	}
	while(i<=mid){
		c[d][k]=c[d+1][i];
		vl=f[d+1][i];
		vr=inf;
		++i;
		fl[d][k]=vl,fr[d][k]=vr;
		if(w[x]<vr)vw[d][k]=true;
		else vw[d][k]=false;
		f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
		++k;
	}
	while(j<=r){
		c[d][k]=c[d+1][j];
		vr=f[d+1][j];
		vl=inf;
		++j;
		fl[d][k]=vl,fr[d][k]=vr;
		if(w[x]<vr)vw[d][k]=true;
		else vw[d][k]=false;
		f[d][k]=min(inf,fl[d][k]+min(w[x],fr[d][k]));
		++k;
	}
}
ll calc(int x,int l,int r,ll rs,int d){
	if(l==r){
		b[++cb]=a[x];
		return 0;
	}
	int mid=l+r>>1;
	int j=r;
	while(j>l&&fl[d][j]+min(w[x],fr[d][j])>rs)--j;
	ll res=0;
	if(rv[c[d][j]]<=mid){
		res=calc(ls(x),l,mid,rs-min(w[x],fr[d][j]),d+1);
		if(vw[d][j]&&rs-fr[d][j]<res)res+=w[x];
		rs-=res;
		res+=calc(rs(x),mid+1,r,rs,d+1);
	}else{
		res=calc(rs(x),mid+1,r,rs-fl[d][j],d+1);
		rs-=res;
		res+=calc(ls(x),l,mid,rs,d+1);
	}
	return res;
}
void solve(){
	scanf("%d%lld",&n,&m);
	tn=1<<n,cb=0;
	for(int i=1;i<tn;++i)scanf("%lld",&w[i]);
	for(int i=0;i<tn;++i){
		scanf("%d",&a[i+tn]);
		rv[a[i+tn]]=i;
	}
	dfs(1,0,tn-1,0);
	calc(1,0,tn-1,m,0);
	for(int i=1;i<=tn;++i)printf("%d%c",b[i]," \n"[i==tn]);
}
int main(){
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}