区间dp，考虑 dp_{l,r} 表示区间的答案，rt_{l,r} 表示这个区间的根。
我们先考虑怎么输出方案，前序遍历先输出根，然后根据根分左右子树，继续递归。
初始化：一个点的答案就是这个点的权值，一个点的根就是他本身。
考虑转移对于，没一个区间枚举根，然后算贡献，答案最大的根，做根。
for(int len=2;len<=n;++len)
for(int l=1;l<=n-len+1;++l)
{
int r=l+len-1;
dp[l][r]=dp[l+1][r]+dp[l][l];
rt[l][r]=l;
for(int k=l+1;k<r;++k)
if(dp[l][k-1]*dp[k+1][r]+dp[k][k]>dp[l][r])
{
dp[l][r]=dp[l][k-1]*dp[k+1][r]+dp[k][k];
rt[l][r]=k;
}
}