好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

原题来自：NOIP 2003

设一个 $n$ 个节点的二叉树 $tree$ 的中序遍历为 $(1,2,3,\dots,n)$，其中数字 $1,2,3,\dots,n$ 为节点编号。每个节点都有一个分数（均为正整数），记第 $i$ 个节点的分数为 $d_i$。$tree$ 及它的每个子树都有一个加分，任一棵子树 $subtree$（也包含 $tree$ 本身）的加分计算方法如下：

记 $subtree$ 的左子树加分为 $l$，右子树加分为 $r$，$subtree$ 的根的分数为 $a$，则 $subtree$ 的加分为：

$$l \times r + a$$

若某个子树为空，规定其加分为 $1$。叶子的加分就是叶节点本身的分数（此时左右子树为空，加分 = $1\times 1 + a = a+1$？实际上叶子定义是左右子树为空，按公式：$l=1, r=1, a=d_i$，加分 = $1\times 1 + d_i = d_i + 1$？但题目说“叶子的加分就是叶节点本身的分数”，说明这里公式中空子树加分为 $1$，但整体计算时，叶子的加分 = 节点分数，所以可能公式理解应为：加分 = $l\times r + a$，且当左右子树为空时 $l=1, r=1$，因此加分 = $1\times 1 + a = a+1$，这与“叶子的加分就是叶节点本身的分数”矛盾。
正确理解是：题目中“不考虑它的空子树”意味着计算加分时，如果子树为空，则其加分不计入乘积，而是视作乘数 $1$，即 $l$ 或 $r$ 为 $1$，所以公式为 $l\times r + a$ 中，$l$ 或 $r$ 为空则为 $1$，从而叶子加分 = $1\times 1 + a = a + 1$ 与“叶子加分就是叶节点本身的分数”不一致，可能是表述问题，实际按样例验证可知公式为 $l\times r + a$，且空子树加分 $=1$。

试求一棵符合中序遍历为 $(1,2,3,\dots,n)$ 且加分最高的二叉树 $tree$。

要求输出：

1. $tree$ 的最高加分；
2. $tree$ 的前序遍历。

---

输入格式

第一行一个整数 $n$ 表示节点个数；

第二行 $n$ 个空格隔开的整数，表示各节点的分数 $d_i$。

---

输出格式

第一行一个整数，为最高加分 $b$；

第二行 $n$ 个用空格隔开的整数，为该树的前序遍历。

---

样例

样例输入

5
5 7 1 2 10

样例输出

145
3 1 2 4 5

样例解释

节点分数：$[5,7,1,2,10]$，中序遍历对应节点 $1,2,3,4,5$。

最高加分 $145$ 对应的树结构为：

• 根节点为 $3$；
• 左子树包含节点 $1,2$（根为 $1$，右子为 $2$）；
• 右子树包含节点 $4,5$（根为 $4$，右子为 $5$）。

计算加分：

• 节点 2（叶子）：加分 $1\times 1 + 7 = 8$
• 节点 1（左空，右为 2）：加分 $1\times 8 + 5 = 13$
• 节点 5（叶子）：加分 $1\times 1 + 10 = 11$
• 节点 4（左空，右为 5）：加分 $1\times 11 + 2 = 13$
• 节点 3（左为子树1-2，右为子树4-5）：加分 $13\times 13 + 1 = 169 + 1 = 170$？不对，题目输出是145，说明我计算有误。
  正确应为：

  • 节点 2：$1\times 1 + 7 = 8$

  • 节点 1：$1\times 8 + 5 = 13$

  • 节点 5：$1\times 1 + 10 = 11$

  • 节点 4：$1\times 11 + 2 = 13$

  • 节点 3：$13\times 13 + 1 = 169+1=170$，不对，应得 145。
    说明公式理解可能不对。实际上，空子树加分规定为 $1$，但叶子节点左右子树为空，加分 = 节点分数本身，而不是 $1\times 1 + a$。所以可能公式是：
    加分 = 左子树加分 × 右子树加分 + 根分数，且空子树加分 = 0？但那样叶子加分 = 0×0 + a = a，符合“叶子加分就是叶节点分数”。
    但题目说“若某个子树为空，规定其加分为 1”，如果空子树加分 = 1，则叶子加分 = 1×1 + a = a+1 ≠ a，矛盾。
    实际上正确解释是：题目中“叶子的加分就是叶节点本身的分数”是指不考虑公式，直接等于分数，而公式中的空子树加分=1仅用于非叶节点计算，但这样不一致。根据样例反推，空子树加分应为 $1$，但这样叶子加分 = a+1，样例中总分 145 可以通过正确 DP 得到。

    经过推导，采用 DP 公式 $dp[i][j] = \max_{i\le k\le j} \{ dp[i][k-1] \times dp[k+1][j] + a[k] \}$，且 $dp[i][i] = a[i]$，$dp[i][i-1] = 1$ 用于空子树。

    对样例：

    • 长度 1：$dp[1][1]=5, dp[2][2]=7, dp[3][3]=1, dp[4][4]=2, dp[5][5]=10$
    • 长度 2：$dp[1][2] = \max(dp[1][0]\times dp[2][2]+a[1], dp[1][1]\times dp[3][2]+a[2])$，注意 $dp[1][0]=1, dp[3][2]=1$
      $= \max(1\times 7+5, 5\times 1+7) = \max(12, 12) = 12$
      $dp[2][3] = \max(1\times 1+7, 7\times 1+1) = 8$
      类似计算得到最终 $dp[1][5] = 145$。

    前序遍历：根 $k=3$，左 $[1,2]$，右 $[4,5]$。
    在 $[1,2]$ 中根是 $1$（因为 $dp[1][2]$ 取 $k=1$），右子 $2$。
    在 $[4,5]$ 中根是 $4$，右子 $5$。
    所以前序：3 1 2 4 5。

---

数据范围

对于 $100\%$ 的数据：

• $n < 30$
• $b < 100$
• 结果不超过 $4\times 10^9$

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 区间 DP 问题，类似 最优二叉搜索树。

设 $dp[i][j]$ 表示中序遍历为 $i..j$ 的子树的最高加分，$root[i][j]$ 表示该子树的根节点。

状态转移：

$$dp[i][j] = \max_{i \le k \le j} \{ dp[i][k-1] \times dp[k+1][j] + a[k] \}$$

其中 $dp[i][i] = a[i]$，$dp[i][i-1] = 1$（空子树）。

记录 $root[i][j]$ 为取得最大值时的 $k$。

前序遍历输出：递归输出 $root[1][n]$ 及左右子树。

复杂度 $O(n^3)$，$n<30$ 可过。