P1040 [NOIP 2003 Senior] Scoring Binary Tree

Let a binary tree $\text{tree}$ with $n$ nodes have an inorder traversal of $(1, 2, 3, \ldots, n)$, where $1, 2, 3, \ldots, n$ are the node indices. Each node has a positive integer score; denote the score of node $i$ as $d_i$. The tree and each of its subtrees have a score. For any subtree $\text{subtree}$ (including $\text{tree}$ itself), its score is computed as follows: score of the left subtree of $\text{subtree}$ $\times$ score of the right subtree of $\text{subtree}$ $+$ score of the root of $\text{subtree}$. If a subtree is empty, its score is defined as $1$. The score of a leaf equals the score of the leaf node itself; its empty children are not considered. Find a binary tree $\text{tree}$ whose inorder traversal is $(1, 2, 3, \ldots, n)$ and whose score is maximized. Output: 1. The maximum score of $\text{tree}$. 2. The preorder traversal of $\text{tree}$.

The first line contains one integer $n$, the number of nodes. The second line contains $n$ space-separated integers, the score of each node.

The first line contains one integer, the maximum score ($Ans \le 4,000,000,000$). The second line contains $n$ space-separated integers, the preorder traversal of the tree.

Constraints For all testdata, it is guaranteed that $1 \le n < 30$, each node’s score is a positive integer less than $100$, and the answer does not exceed $4 \times 10^9$. Translated by ChatGPT 5