設(shè)一個n個節(jié)點的二叉樹tree的中序遍歷為（l,2,3,…,n），其中數(shù)字1,2,3,…,n為節(jié)點編號。每個節(jié)點都有一個分數(shù)（均為正整數(shù)），記第j個節(jié)點的分數(shù)為di，tree及它的每個子樹都有一個加分，任一棵子樹subtree（也包含tree本身）的加分計算方法如下：         

subtree的左子樹的加分×  subtree的右子樹的加分＋subtree的根的分數(shù)         

若某個子樹為主，規(guī)定其加分為1，葉子的加分就是葉節(jié)點本身的分數(shù)。不考慮它的空 子樹。        

 試求一棵符合中序遍歷為（1,2,3,…,n）且加分最高的二叉樹tree。要求輸出；         

（1）tree的最高加分         

（2）tree的前序遍歷

第1行：一個整數(shù)n（n＜30），為節(jié)點個數(shù)。         

第2行：n個用空格隔開的整數(shù)，為每個節(jié)點的分數(shù)（分數(shù)＜100）。

第1行：一個整數(shù)，為最高加分（結(jié)果不會超過4,000,000,000）。        

 第2行：n個用空格隔開的整數(shù)，為該樹的前序遍歷。

5
5 7 1 2 10

145
3 1 2 4 5