看到题目名字：“……二叉树”，看到式子“左子树加分 \(\times\) 右子树加分 \(+\) 根节点加分”——哦，树形dp。
然而事实并非如此，注意到题目给出的是树的中序遍历，即“左儿子 \(\rightarrow\) 根 \(\rightarrow\) 右儿子”形的表示，我们发现其与区间 dp 相性更好，因为在这种遍历下，一棵子树是完整的一个区间，树上父子间转移可以无缝切换到区间的合并！
有了上面的转化，我们可以比较套路的设计状态：\(f_{i,j}\) 表示区间 \([i,j]\) （对应的子树）的加分，其转移方程为 \(f_{i,j}=f_{i,k-1}\times f_{k+1,j}+f_{k,k}\)（\(k\) 在 \([i,j]\) 内枚举根节点），基本上照抄题面。初始化即将点 \(i\) 加分赋给 \(f_{i,i}\)，答案即为 \(f_{1,n}\)。
前序遍历可以顺带记录，设 \(root_{i,j}\) 表示区间 \([i,j]\)（对应的子树）的根，如果 \(f\) 数组更新，则同时更新 \(root\)。最后按"根 \(\rightarrow\) 左儿子 \(\rightarrow\) 右儿子”顺序递归输出。
题目明确提醒了 \(Ans\le 4\times 10^9\)，不会有人不开 long long 吧。
下面是去掉了缺省源的 AC 代码：
void print(int i,int j){
if(i>j) return;
printf("%d ",rt[i][j]);//输出根
if(i!=j) print(i,rt[i][j]-1),print(rt[i][j]+1,j);//先左后右
}
int main(){
n=read();
rep(i,1,n) f[i][i]=read(),rt[i][i]=i;
rep(len,2,n) rep(i,1,n-len+1){
int j=i+len-1;
f[i][j]=f[i][i]+f[i+1][j],rt[i][j]=i;//从左子树为空开始
rep(k,i+1,j-1) if(f[i][j]<f[i][k-1]*f[k+1][j]+f[k][k])//枚举根节点
f[i][j]=f[i][k-1]*f[k+1][j]+f[k][k],rt[i][j]=k;
}
printf("%lld\n",f[1][n]),print(1,n);
return 0;
}