#475. 加分二叉树

加分二叉树

题目描述

原题来自:NOIP 2003

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

subtree 的左子树加分为 l\red{l},右子树加分为 r\red{r}subtree 的根的分数为 a\red{a},则 subtree 的加分为:

l×r+a\red{l\times r+a}

若某个子树为空,规定其加分为1\red{ 1},叶子的加分就是叶节点本身的分数。不考虑它的空子树。

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

要求输出:

1\red{1}. tree 的最高加分;

2\red{2}. tree 的前序遍历。

输入格式

第一行一个整数n\red{ n }表示节点个数;

第二行n\red{ n }个空格隔开的整数,表示各节点的分数。

输出格式

第一行一个整数,为最高加分b\red{ b}

第二行n\red{ n} 个用空格隔开的整数,为该树的前序遍历。

样例

输入样例

5
5 7 1 2 10

输出样例

145
3 1 2 4 5

提示

对于100%\red{ 100\%} 的数据,n<30,b<100\red{n\lt 30,b\lt 100},结果不超过 4×109\red{4\times 10^9}

统计

相关

在以下作业中:

DP