SP17406 GCJ082A - Cheating a Boolean Tree

在这个问题中，我们会研究一种特殊的二叉树，称为布尔树。在这样的树中，除了可能的最后一层（最深的一层），每一层都是完全填满的，而且最后一层的节点都尽量向左排布。另外，这棵树中的每个节点要么没有孩子，要么有两个孩子。 布尔树的特别之处在于，每个节点都有一个关联的布尔值，即 1 或 0。此外，每个内部节点同样有一个关联的逻辑门：“AND” 或 “OR”。“AND”门节点的值是其两个子节点的值通过逻辑与操作得到的。“OR”门节点的值是通过其两个子节点的值做逻辑或操作得到的。叶节点的值会作为输入给出，以便可以从底至上计算整个树上所有节点的值。 我们特别关心的是树的根节点。我们希望根节点的值是 **V**，即 0 或 1。然而，这并不一定是根节点实际计算所得的值。好在我们可以调整某些节点的逻辑门类型：可以将“AND”门改为“OR”门，反之亦然。 现在，给定一棵布尔树的详细描述以及说明哪些逻辑门是可以被改变的，要求计算出使根节点的值为 **V** 所需更改的最少门数。如果无法实现这一目标，则输出「IMPOSSIBLE」。

输入的第一行是整数 **N**，表示测试用例的数量。接下来是 **N** 个测试用例。 每个测试用例以两个整数 **M** 和 **V** 开头。**M** 是树中的节点数，确保为奇数，以便所有节点都有 0 个或 2 个孩子。**V** 是期望的根节点值，取值为 0 或 1。 接下来 **M** 行描述这棵树的节点。第 X 行描述编号为 X 的节点，从节点 1 开始编号。 前 (**M**−1)/2 行描述的是内部节点。每行含有两个整数 **G** 和 **C**，它们都是 0 或 1。当 **G** 为 1 时，该节点的逻辑门是“AND”；否则是“OR”。当 **C** 为 1 时，该节点的门类型可以被改变，否则不可改变。内部节点 X 的两子节点分别为 2X 和 2X+1。 接下来的 (**M**+1)/2 行描述的是叶节点。每行为一个整数 **I**，即其布尔值，取值为 0 或 1。

对于每个测试用例，输出格式为： `Case #X: Y` 其中 **X** 是测试用例的编号，从 1 开始。**Y** 是将根节点的值调整为 **V** 所需（更改）的最少门数；如果无法实现则输出「IMPOSSIBLE」。 ### 样例输入输出 #### 输入 ``` 2 9 1 1 0 1 1 1 1 0 0 1 0 1 0 1 5 0 1 1 0 0 1 1 0 ``` #### 输出 ``` Case #1: 1 Case #2: IMPOSSIBLE ``` **本翻译由 AI 自动生成**