切り方は tree に対応する． つまり，最適な切り方を探すのは，最適な tree を探すことに対応する． しかし，tree 全体は探索しても間に合わない．
Tree の葉に値を割り振って，parent に child の値を足していくと考える． すると，葉を除いた頂点に書かれた値の合計は， 葉の深さ*葉の値の合計と一致する． よって，葉が深い場所にあるものに対して小さい値を割り振るのが最適．
実装
切っていくというよりは，つなげていく方針． 深い場所から和を取っていく． 小さい方から2つをとって和をとるので，priority queue で実装できる．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n,l;
cin >> n >> l;
vll a(n); rep(i,n) { cin >> a[i]; }
min_priority_queue<ll> q;
rep(i,n){
q.push(a[i]);
l -= a[i];
}
if(l > 0) q.push(l); // rem: l > 0
ll ans = 0;
while(q.size() != 1){
ll x = q.top(); q.pop();
ll y = q.top(); q.pop();
ans += x+y;
q.push(x+y);
}
cout << ans << endl;
return 0;
}
