这道题如果不让输出方案的话，和普通的区间DP差不多。输出方案的话，我是直接把这颗树重建了，然后bfs一下输出的

#pragma GCC optimize(2)
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <climits>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

int n,a[310];
int f[310][310];
int path[310][310];

int l[310],r[310];

int dfs(int i,int j)
{
    if(i>=j) return -1;

    int root=path[i][j];

    l[root]=dfs(i,root);
    r[root]=dfs(root+1,j);
    return root;
}

void bfs(int h){
    queue<int> q;
    q.push(h);
    vector<int> v;
    while(q.size())
    {
        int x=q.front();q.pop();
        v.push_back(x);

        if(~l[x]) q.push(l[x]);
        if(~r[x]) q.push(r[x]);
    }
    for(auto i:v) cout<<i<<' ';
}

int main()
{
    memset(f,-0x3f,sizeof f);
    memset(path,-1,sizeof path);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int len=1;len<=n;len++)
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(len==1) f[i][j]=0;
            else
            {
                for(int k=i;k<j;k++)
                {
                    int x=f[i][k];
                    int y=f[k+1][j];
                    if(f[i][j]<(a[i]+a[j])*a[k]+x+y)
                    {
                        f[i][j]=(a[i]+a[j])*a[k]+x+y;
                        path[i][j]=k;
                    }
                }
            }
        }
    cout<<f[1][n]<<endl;
    int h=dfs(1,n);
    bfs(h);

    return 0;
}