Atcoder C問コード解説のお願い（JS）

前提・実現したいこと

Atcoderの問題で、AC済のコードがわからなかったためその解説をお願いしたいです。
解説のyoutubeにある二分木や何を求めるべきなのか、その二分木が存在しない場合などは把握しています。
コード上に記述してある”//ここまでは理解しています”以降からコード解説をお願いしたいです。
宜しくお願いいたします。

問題：
https://atcoder.jp/contests/nomura2020/tasks/nomura2020_c
解説：
https://img.atcoder.jp/nomura2020/editorial.pdf
https://www.youtube.com/watch?v=NuhtAfH5SCc&feature=youtu.be

AC済のコード

"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.trim().split(/ |\n/), cid = 0;

function main() {
    let N = +cin.shift();
    let A = cin.map(x => +x);
    let node = Array(N + 1);
    node[0] = 1;
    for (let d = 0; d < N; d++) {
        node[d + 1] = (node[d] - A[d]) * 2;
        if (node[d + 1] < A[d + 1]) {
            console.log(-1);
            return;
        }
    }
    //console.log(sum(node));

　　//ここまでは理解しています

    if (node[N] < A[N]) {
        console.log(-1);
    } else if (node[N] == A[N]) {
        console.log(sum(node));
    } else {
        // node[d] が多すぎた場合。枝を逆に減らしていく必要がある。
        let nodemax = Array(N + 1);
        nodemax[N] = A[N];
        for (let d = N; d > 0; d--) {
            //console.log({ d, A, node, nodemax}, sum(node));
            if (nodemax[d] < node[d]) {
                node[d] = nodemax[d];
                nodemax[d - 1] = node[d] + A[d - 1];
            }
        }
        if (nodemax[0] < node[0]) {
            node[0] = nodemax[0];
        }
        console.log(sum(node));
    }
}
var sum = function (arr) {
    var sum = 0n;
    arr.forEach(function (elm) {
        sum += BigInt(elm);
    });
    return sum.toString();
};
main();

試したこと

・二分木の理解
・JSのコードを一つ一つ検索
・途中まで（エラー出力まで）は理解

行動規範の内容に同意します

回答1件

ベストアンサー

まず、ここまでは理解、と書かれているnodeの計算は、深さd <= N-1までにおける最大限取りうる頂点の数を示していることはわかっていると思います。ただし、node[N]の頂点の数は命題を満たしません。

そこで、今度は深さをNから逆順にたどり、命題を満たす最大限の頂点の数を計算します。
（逆順からたどっていくと頂点から1本しか枝が伸びていない状態が最大限の頂点数になる）

深さd (0 < d < n-1)における最小限の頂点の数は、その次の深さd+1の頂点数と深さdにおける葉のない頂点数A(d)に一致します。この値をnodemax[d]とし、深さdにおける最終的な頂点数をmin(node[d],nodemax[d])で求めて、node[d]へ代入していきます。
以下に図示すると、赤丸で囲ったノード数の足し算をしているイメージです。