【统一省选2024】迷宫守卫 - 题目

Alice 拥有一座迷宫，这座迷宫可以抽象成一棵拥有 $2^{n}$ 个叶节点的满二叉树，总节点数目为 $(2^{n + 1} - 1)$ ，依次编号为 $1 \sim (2^{n + 1} - 1)$ 。其中编号为 $2^{n} \sim (2^{n + 1} - 1)$ 的是叶节点，编号为 $1 \sim (2^{n} - 1)$ 的是非叶节点，且非叶节点 $1 \leq u \leq (2^{n} - 1)$ 的左儿子编号为 $2 u$ ，右儿子编号为 $(2 u + 1)$ 。

每个非叶节点都有一个石像守卫，初始时，所有石像守卫均在沉睡。唤醒 $u$ 点的石像守卫需要 $w_{u}$ 的魔力值。

每个叶节点都有一个符文， $v$ 点的符文记作 $q_{v}$ 。保证 $q_{2^{n}}, q_{2^{n} + 1}, \dots, q_{2^{n + 1} - 1}$ 构成 $1 \sim 2^{n}$ 的排列。

探险者初始时持有空序列 $Q$ ，从节点 $1$ 出发，按照如下规则行动：

到达叶节点 $v$ 时，将 $v$ 点的符文 $q_{v}$ 添加到序列 $Q$ 的末尾，然后返回父节点。
到达非叶节点 $u$ 时：
- 若该点的石像守卫已被唤醒，则只能先前往左儿子，（从左儿子返回后）再前往右儿子，（从右儿子返回后）最后返回父节点。
- 若该点的石像守卫在沉睡，可以在以下二者中任选其一：
  - 先前往左儿子，再前往右儿子，最后返回父节点。
  - 先前往右儿子，再前往左儿子，最后返回父节点。

返回节点 $1$ 时，探险结束。可以证明，探险者一定访问每个叶节点各一次，故此时 $Q$ 的长度为 $2^{n}$ 。

探险者 Bob 准备进入迷宫，他希望探险结束时的 $Q$ 的字典序越小越好，与之相对，Alice 希望 $Q$ 的字典序越大越好。

在 Bob 出发之前，Alice 可以选择一些魔力值花费之和不超过 $K$ 的石像守卫，并唤醒它们。Bob 出发时，他能够知道 Alice 唤醒了哪些神像。若双方都采取最优策略，求序列 $Q$ 的最终取值。

对于两个长度为 $2^{n}$ 的序列 $Q_{1}, Q_{2}$ ，称 $Q_{1}$ 字典序小于 $Q_{2}$ 当且仅当以下条件成立：

$\exist i \in [1, 2^{n}]$ 满足以下两个条件：
- $\forall 1 \leq j < i ， Q_{1, j} = Q_{2, j}$ ；
- $Q_{1, i} < Q_{2, i}$ 。

输入格式

本题有多组测试数据。输入的第一行包含一个正整数 $T$ ，表示测试数据组数。

接下来依次 $T$ 组测试数据。对于每组测试数据：

第一行两个整数 $n, K$ 表示迷宫规模和 Alice 可用于唤醒石像守卫的魔力值上限。
第二行 $(2^{n} - 1)$ 个整数 $w_{1}, w_{2}, \dots, w_{2^{n} - 1}$ 表示唤醒各个石像守卫耗费的魔力值。
第三行 $2^{n}$ 个整数 $q_{2^{n}}, q_{2^{n} + 1}, \dots, q_{2^{n + 1} - 1}$ 表示各个叶节点上的符文。

输出格式

对于每组数据，输出一行 $2^{n}$ 个整数 $Q_{1}, Q_{2}, \dots, Q_{2^{n}}$ ，表示双方都采取最优策略的情况下，序列 $Q$ 的最终取值。

样例 1

input

3
1 0
1
2 1
1 1
1
2 1
3 3
3 2 1 2 1 2 1
4 2 6 3 7 1 5 8

output

1 2
2 1
2 4 6 3 5 8 7 1

explanation

第一组数据中，Alice 无法唤醒石像守卫，Bob 可以选择先访问叶节点 $3$ ，再访问叶节点 $2$ ，得 $Q = {1, 2}$ 。
第二组数据中，Alice 可以唤醒节点 $1$ 的石像守卫，Bob 只能先访问叶节点 $2$ ，再访问叶节点 $3$ ，得 $Q = {2, 1}$ 。
第三组数据中，Alice 的最优策略是唤醒节点 $5, 6$ 的石像守卫。

【样例 2】

见附件中的 maze2.in/ans。

该组数据满足特殊性质 A。

【样例 3】

见附件中的 maze3.in/ans。

该组数据满足特殊性质 B。

【样例 4】

见附件中的 maze4.in/ans。

【样例 5】

见附件中的 maze5.in/ans。

子任务

设 $\sum 2^{n}$ 表示单个测试点钟所有测试数据的 $2^{n}$ 的和。对于所有测试数据，保证

$1 \leq T \leq 100$ ；
$1 \leq n \leq 16$ ， $1 \leq \sum 2^{n} \leq 10^{5}$ ；
$0 \leq K \leq 10^{12}$
$\forall 1 \leq u \leq (2^{n} - 1)$ ， $0 \leq w_{u} \leq 10^{12}$ ；
$q_{2^{n}}, q_{2^{n} + 1}, \dots, q_{2^{n + 1} - 1}$ 构成 $1 \sim 2^{n}$ 的排列。

测试点编号	$n \leq$	$\sum 2^{n} \leq$	特殊性质
$1 \sim 5$	$4$	$80$	无
$6$	$6$	$200$	A
$7 \sim 8$	$6$	$200$	B
$9 \sim 10$	$6$	$200$	无
$11$	$11$	$4000$	A
$12 \sim 13$	$11$	$4000$	B
$14 \sim 15$	$11$	$4000$	无
$16$	$16$	$10^{5}$	A
$17 \sim 18$	$16$	$10^{5}$	B
$19 \sim 20$	$16$	$10^{5}$	无

特殊性质 A： $\forall 2^{n} \leq v \leq (2^{n + 1} - 1)$ ， $q_{v} = (2^{n + 1} - v)$ 。

特殊性质 B： $\forall 1 \leq u \leq (2^{n} - 1)$ ， $w_{u} = 1$ 。

时间限制： $0.5s$

空间限制： $512MB$

Universal Online Judge

UOJ

#868. 【统一省选2024】迷宫守卫