P15515 [BalticOI 2003] Register Allocation (Day 2)

现代计算机处理器的寄存器数量是有限的——寄存器是通用的存储位置，其速度显著快于主存储器。执行计算的操作（例如加法、乘法等）要求其参数位于寄存器中，并在寄存器中返回结果。 在本题中，我们考虑表达式求值的寄存器分配问题。在编译器内部，一个表达式被表示为一棵树。树的叶节点对应必须从主存加载的值。中间（非叶）节点对应操作，每个中间节点的子节点数等于该操作的参数个数。显然，在执行一个操作之前，所有参数的值都必须可用。 由于寄存器数量有限，编译器必须决定哪些中间结果保留在寄存器中（在需要时可以立即使用），哪些中间结果存入主存（在需要时必须再加载回来）。改变某个操作的参数求值顺序也可能是有用的（这也是为什么大多数高级语言不保证任何特定的求值顺序）。 你的任务是编写一个程序：给定一棵表达式树，找出总成本最小的寄存器分配方案和求值顺序。

输入的第一行包含寄存器数量 $N$（$1 \le N \le 100$）。第二行包含两个整数：从主存加载一个值到寄存器的代价 $C_l$（$1 \le C_l \le 100$），以及从寄存器把一个值存入主存的代价 $C_s$（$1 \le C_s \le 100$）。输入其余部分描述表达式树，从根节点开始： - 第一行包含该节点的子节点数 $K_x$（$0 \le K_x \le 10$ 且 $K_x \le N$）； - 若 $K_x = 0$，则这是一个叶节点，描述结束； - 若 $K_x > 0$，则这是一个中间节点，并且： - 下一行包含一个整数：该节点所表示操作的代价 $C_x$（$1 \le C_x \le 100$）； - 随后按照同样的方式给出 $K_x$ 棵子树的描述。 节点按它们在输入中出现的顺序从 $1$ 到 $M$ 编号。可以假设 $M \le 10\ 000$。

输出的第一行必须包含计算该表达式的最小代价。输出的其余部分必须对表达式树中的每个中间节点输出一行。每行必须包含两个整数：第一个是要计算的节点编号，第二个为 $1$ 表示结果应保留在寄存器中，或为 $0$ 表示结果应存入主存（并将代价 $C_s$ 也加入总计算代价中）。 为确保表达式求值的总成本尽可能小，操作必须按应执行的顺序列出，并满足以下条件： - 只有在一个节点的所有子节点都已计算之后，该节点才能被计算； - 对于将要执行的操作，其参数中不在寄存器里的值都必须从主存加载（每个值的代价为 $C_l$）； - 执行该操作时用于存放参数的寄存器可以立即重用，尤其可以用于存放该操作的结果。 如果存在多个最小代价的方案，输出其中任意一个即可。

下图说明了上面的输入：两棵树都对应同一个表达式树，其中左边的树显示中间节点的代价，右边的树显示节点的编号。  上面输出中的求值方案的代价为 $(C_l + C_l + 15 + C_s) + (C_l + C_l + 5) + (C_l + 10) = 47$。 你将获得一个程序 $\tt REGSCHECK$，它会验证 $\tt REGS.OUT$ 相对于 $\tt REGS.IN$ 的正确性（但不验证最优性），并给出有信息量的错误消息。