2143: 宝典2第十一章加分二叉树

【题目描述】加分二叉树（tree.cpp/c/pas)NOIP 2003

科技忽略了过程就是魔法，魔法展示了过程就是科技。例如，在魔法世界彪炳史册的艾萨克·牛顿爵士，就被称为“最初的科学家，最后的炼金术士”。魔法世界的所谓魔法，其本质就是科技，只不过因为在远古时代发生的几次战乱，导致相当数量尖端科技理论的遗失和残缺，使得人们只知道如何使用科技却无法解释其原理，只好统称为魔法而已。所以魔法世界的科技树在宇宙各种文明的发展中，可以抽象的看成一颗奇怪的具有n个节点的二叉树tree，树的中序遍历为（l，2，3，…，n），其中数字1，2，3，…，n为节点编号。每个节点都有一个分数（均为正整数），记第i个节点的分数为di，tree及它的每个子树都有一个加分，任一棵子树subtree（也包含tree本身）的加分计算方法如下： subtree的左子树的加分× subtree的右子树的加分＋subtree的根的分数。若某个子树为空，规定其加分为1，叶子的加分就是叶节点本身的分数。不考虑它的空子树。 试求一棵符合中序遍历为（1，2，3，…，n）且加分最高的二叉树tree。要求输出：　

（1）tree的最高加分。

（2）tree的前序遍历。

【输入格式】

 第1行：一个整数n（n＜30），为节点个数。 第2行：n个用空格隔开的整数，为每个节点的分数（分数＜100）。

【输出格式】

 第1行：一个整数，为最高加分（结果不会超过4000 000 000）。 第2行：n个用空格隔开的整数，为该树的前序遍历。

【输入样例】

5

5 7 1 2 10

【输出样例】

145

3 1 2 4 5