CF2261H Oh Tree Tree Tree, No Need to Leave

这是一道通信类问题。 有两位玩家：玩家 A（Isabel）和玩家 B（Tara）。评委会首先与玩家 A 交互。在玩家 A 结束交互后，评委会将与玩家 B 交互。注意，玩家 A 和玩家 B 不能直接相互传递信息；两位玩家只能通过评委会发送信息或接收信息，但她们可以预先约定用于通信的策略。 Isabel 想要向 Tara 发送一个长度为 $n$ 的二进制字符串 $b$。她可以利用一棵高度为 $h$ 的完全二叉树（正好有 $2^h-1$ 个节点）进行信息传递。树的所有节点都用从 $1$ 到 $2^h-1$ 的整数标号，其中 $1$ 号节点是根节点，对于每个非叶子节点 $v$，左孩子标号为 $2v$，右孩子标号为 $2v+1$。 Isabel 会在每个节点上写一个二进制值（$0$ 或 $1$）。写完后，她将整棵树发送给 Tara。 然而，她们的死敌 Lord Verity 将试图破坏她们的通信。在 Isabel 写完所有节点的数值后，Lord Verity 会按以下顺序执行操作，每种操作只执行一次： 1. 他选择某个节点 $u$。 2. 他翻转 Isabel 在该节点 $u$ 上写的值。如果原来是 $0$，就改为 $1$，反之亦然。 3. 如果 $u$ 是叶子节点，则不做其他操作。否则，他会交换 $u$ 的两个子指针，即左孩子和右孩子同时交换。之后，所有节点重新标号，使得 $1$ 号节点为根节点；对于任意非叶节点 $v$，左孩子编号为 $2v$，右孩子编号为 $2v+1$。 注意，Lord Verity 的操作可能是自适应的。这意味着他选择要“捣乱”的节点并不是预先确定的，而是可以基于 Isabel 写下的信息内容做出选择。 在 Lord Verity 捣乱后，Tara 会收到修改后的二叉树结构以及每个节点的二进制值，但她并不知道 Lord Verity 捣乱的是哪一个节点。准确来说，她会收到一个新的二进制字符串 $l$，其中 $l_u$ 为所有节点重新标号后，第 $u$ 号节点的数值。 Tara 的任务是还原最初被 Isabel 想要传递的原始字符串 $b$。 $n$、$h$ 的取值只会有两种组合： - $n = 1, h = 2$ - $n = 2030, h = 11$ 第一种组合仅用于样例测试，并提供了正确的通信策略。

你的代码会在每个测试上运行两次。第一次运行你是 Isabel，第二次你是 Tara。 第一次运行输入 输入的第一行包含字符串 first，表示第一次运行（你是 Isabel）。 每个测试包含多组测试数据。第一行包含测试组数 $t$，$1 \le t \le 1024$。随后描述每组测试数据。 每组测试数据的第一行包含两个整数 $n$ 和 $h$（$n = 1$ 且 $h = 2$，或者 $n = 2030$ 且 $h = 11$），分别表示字符串 $b$ 的长度和二叉树的高度。注意，$n = 1$ 且 $h = 2$ 只在样例中出现，正式测试不会出现。 接下来一行是一个长度为 $n$ 的二进制字符串 $b$。 第二次运行输入 输入的第一行包含字符串 second，表示第二次运行（你是 Tara）。 每个测试包含多组测试数据。第一行包含测试组数 $t$，$1 \le t \le 1024$。随后描述每组测试数据。注意，本次测试组数与第一次输入时的 $t$ 保持一致。 每组测试数据的第一行同样包含两个整数 $n$ 和 $h$，即字符串 $b$ 的长度和对应树的高度。测试组顺序可能与第一次不一致。 每组接下来一行包含一个长度为 $2^h-1$ 的二进制字符串，表示每个节点的数值 $l_1,l_2,\ldots,l_{2^h-1}$。$l_i$ 表示所有操作后第 $i$ 号节点上的值（经过重新标号）。 注意：Lord Verity 捣乱后，节点标号会与 Isabel 发送前的编号不同。 Hack 数据格式 Hack 时使用如下格式。 第一行一个整数 $t$，$1 \le t \le 1024$，表示测试组数。 每组测试数据的第一行包含三个整数 $n, h, p$（$n = 2030$，$h = 11$，$1 \le p \le 2^h-1$），依次为字符串 $b$ 的长度、树的高度、Lord Verity 要捣乱的节点编号。编号 $p$ 指的是 Isabel 发送前的树的编号。 接下来一行为长度为 $n$ 的二进制字符串 $b$，即 Isabel 要发送的原始字符串。 注意，Hack 时 Lord Verity 不会自适应：他无论 Isabel 写什么，始终选择编号 $p$ 的节点。

第一次运行输出 对于每组测试数据，输出一个长度为 $2^h-1$ 的二进制字符串，第 $i$ 位表示 Isabel 在编号 $i$ 的节点上设置的二进制值。 第二次运行输出 对于每组测试数据，输出 Tara 所猜测的原始字符串 $b$（长度为 $n$）。

当 $n=1$ 时，一种正确的通信策略如下。 Isabel 只需传递 $1$ 位，但有 $2^h-1=3$ 个节点可用。由于 Lord Verity 只能干扰一个节点，最简单的方法是 Isabel 将 $b_1$ 的值写在树的所有节点上。这样，无论 Lord Verity 捣乱哪个节点，Tara 只需输出 $l$ 中出现频率最多的那个值即可。 请参考样例。注意，第一、二次运行时测试用例的顺序可能不同。这里，为了示范，两组样例顺序发生了调换。 Isabel 和 Tara 只针对 $b = 0$ 使用上述策略：Isabel 将所有节点写为 $0$，输出 $000$。Lord Verity 捣乱编号为 $3$ 的节点，于是 Tara 收到 $l = 001$。此时，$l$ 中 $0$ 出现次数最多，Tara 输出 $0$。 另外一个 $b = 1$ 的例子仅为说明 Lord Verity 的操作效果。具体地，Isabel 将编号 $1$、$3$ 的节点写为 $1$，$2$ 号节点写为 $0$。Lord Verity 操作编号 $1$ 的节点，首先将其值变为 $0$，然后交换左右子树并重新编号：此时 $2$ 号节点变为 $3$ 号，$3$ 号节点变为 $2$ 号。所以最终 $l = 010$。Tara 也能正确还原出 $b = 1$。 重要提示：以上样例中，Lord Verity 选择了 $1$ 和 $3$ 号节点。但你代码实际运行时，Lord Verity 不一定选择同样的节点，所以样例的具体输出内容不能直接照搬。 由 ChatGPT 5 翻译