D1-Lsxszc爱出题（tree）

题目背景

Lsxszc是一个失败的出题人，但他还是喜欢出题。他想要出一道完美的，标新立异的，无懈可击的贪心题目，但是他一直没有灵感，直到他遇到了一道树上问题，他灵感迸发，就决定是你了！！！

题目描述

本题有多次测试！

存在一棵初始为空，深度为 $n$ 的完全二叉树，其节点位置编号规则为：根节点编号为 1，编号为 $i$ 的节点的左子节点编号为 $2i$，右子节点编号为 $2i+1$。该完全二叉树的位置是预定义的“固定空间”，即使无节点占据也不改变编号规则，最坏情况下（节点构成高度为 $n$ 的树链），需覆盖至少 $2^n -1$ 个位置。

给定序列 $a$（长度 $2^n -1$，可覆盖所有可能被节点占据的位置），其中 $a_i$ 表示完全二叉树中位置 $i$ 的固定权值。

另有 $n$ 个互不相同的节点，每个节点拥有唯一权值 $b_j$（$j=1,2,\dots,n$）。要求将这 $n$ 个节点按照二叉搜索树（BST）规则插入上述完全二叉树：对于树中任意节点，其左子树所有节点的 $b$ 值均小于该节点的 $b$ 值，右子树所有节点的 $b$ 值均大于该节点的 $b$ 值。

插入顺序可任意选择，最终BST结构不唯一（无需占满完全二叉树），但每个节点插入后会占据完全二叉树的唯一位置 $i$。

每个占据位置 $i$ 的节点的贡献为 $b_j \times a_i$，未被节点占据的位置贡献为 0。请选择最优的节点插入顺序，使得所有节点的贡献之和最大。

输入格式

$T$

$n_1$

$a_1 \ \ a_2 \ \ \dots \ \ a_{2^{n_1}-1}$

$b_1 \ \ b_2 \ \ \dots \ \ b_{n_1}$

$\dots$

$n_T$

$a_1 \ \ a_2 \ \ \dots \ \ a_{2^{n_T}-1}$

$b_1 \ \ b_2 \ \ \dots \ \ b_{n_T}$

输出格式

共 $T$ 行，每行一个整数，表示该测试所有节点贡献之和的最大值。

输入输出样例 #1

输入 #1

1
2
10 20 30
5 10

输出 #1

350

说明/提示

样例说明

共有两种安排顺序：

1. 5 10：5先插入，贡献为 $5 \times 10 =50$，10后插入，贡献为 $10 \times 30=300$，总贡献为 $350$
2. 10 5：10先插入，贡献为 $10\times 10=100$，5后插入，贡献为 $5\times 20=100$，总贡献为 $200$。

数据范围

对于 $100\%$ 的数据：

• $1 \le T \le 20$
• $2 \le n \le 16$
• $0 \le a_i \le 10^7$；
• $0 \le b_j \le 10^7$，且所有 $b_j$ 互不相同

后记

Lsxszc真是一个失败的出题人$\dots$