（这一题是最开始出的第二题，所以风格不太一样。给验题的小朋友都震惊了：这是你出的？

所以有人可以get到我出题的艺术吗，这题看着吓人，但是没啥性质。而且我一开始真的想出贪心来着）

题面明确给出Lsxszc是一个失败的出题人，所以直接排除贪心，考虑dp。

平衡二叉树有一个性质：中序遍历是一个有序的序列。所以我们对 b 数组进行排序，然后树中一个节点的左右子节点一定会是序列中左右区间中的某个值。

所以树形dp枚举每一个值可能在完全二叉树中的位置即可。时间复杂度 $O(T \times n^3 \times 2^n)$

树的深度有限制，跑不满。

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

/*
2
10 20 30
5 10
*/

const int MAXN = 16;
long long dp[(1<<MAXN)+1][MAXN][MAXN];
long long b[MAXN];
long long a[(1<<MAXN)+1];
int n, sizea;

long long dfs(int l,int r,int root_pos) 
{
	if(l>r) return 0;
	if(root_pos>((1<<n)-1)) return-1e18;
	if(dp[root_pos][l][r]!=-1) return dp[root_pos][l][r];
	long long maxval = -1e18;
	for(int mid=l; mid<=r; mid++) 
	{
		long long lft=dfs(l,mid-1,root_pos*2);
		long long rig=dfs(mid+1,r,root_pos*2+1);
		if(lft==-1e18 || rig==-1e18) continue;
		long long total=b[mid]*a[root_pos]+lft+rig;
		maxval=max(maxval,total);
	}
	dp[root_pos][l][r]=maxval;
	return maxval;
}

int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--) 
	{
		cin>>n;
		sizea=1<<n;
		for(int i=1;i<sizea;i++) 
		{
			cin>>a[i];
		}
		for(int i=0; i<n; i++) 
		{
			cin>>b[i];
		}
		sort(b,b+n);
		memset(dp,-1,sizeof(dp));
		long long ans=dfs(0,n-1,1);
		cout<<ans<<"\n";
	}
	return 0;
}