SON OF SUN

Bounds for a fixed record set. First maximize the original sum. Fix the indices of negative-energy record vertices as $\mathcal R=\{b_1<\cdots<b_t\}$. Nonrecord negative vertices optimally have depth $1$, while nonrecord positive vertices optimally have the current maximum depth. Promoting positive vertex $i$ to a record increases the value by

When $i\in\mathcal R$, the negative record in the same pair also moves one level deeper and cancels the own term $i$. Consequently, an optimum exists in which every positive vertex is a record. Its value is

Since $b_r\geq r$ and $f_r(x)-f_r(x+1)=3x+r+1>0$, this is at most $F_N(t)$, obtained by the prefix set $\{1,\ldots,t\}$. A nonprefix set has $b_t\geq t+1$ and loses at least $4t+1$ from that bound.

For a prefix set with $t<N$, omitting any positive record loses at least $t+1$. If $i>t$, its own term $i\geq t+1$ remains; if $i\leq t$, the future term $j=N\notin\mathcal R$ remains. Raising a nonrecord negative depth above $1$ also loses at least $t+1$, since its index exceeds $t$. Thus every other value for this prefix set is at most $F_N(t)-t-1$.

For the opposite direction, negate the objective and fix the record set among the originally positive vertices. Originally positive nonrecords optimally have depth $1$, and every originally negative vertex is a record at the optimum. Promoting negative vertex $i$ gives $i+\sum_{j>i,\,j\notin\mathcal R}j>0$. The maximum is

Here $g_r(x)-g_r(x+1)=3x+r-1>0$, so the prefix set gives $B_N(t)$ and a nonprefix set loses at least $4t-1$. For a prefix set with $t<N$, other changes from its optimum lose at least $t+1$. The first originally positive vertex must be a record, but $B_N(1)>B_N(0)$, so including $t=0$ does not change the maximum. These arguments prove both extremum formulas.

Two explicit constructions. Give the first $t$ pairs depths $2i-1,2i$. For each later $i>t$, fixing the positive depth at $i+t$ and choosing the negative depth as $1+b_i$ produces

Conversely, fixing the negative depth at $i+t$ and choosing the positive depth as $1+b_i$ produces

Even if the positive vertex first reaches depth $i+t$, the negative vertex may use an existing parent at depth $i+t-1$ and stay at that same depth. Every choice of the $b_i$ is therefore feasible.

A coin-coverage lemma. Suppose $t\geq1$ and $N\geq2t+1$. There are $i+t-1$ coins of value $i$. Set $a=t+1$, let $C$ be the coin count, and let $W$ be their total value. Their subset sums are exactly

For exactly $q$ coins, every integer between the smallest-$q$ sum $A_q$ and largest-$q$ sum $Z_q$ is attainable. Move the selected indices through the sorted coin sequence from the smallest selection to the largest. Each move changes the sum by $0$ or $1$, since adjacent coin values differ by at most one.

It remains to connect consecutive intervals for $q=1,\ldots,C-2$. Since $Z_q=W-A_{C-q}$, their gap is

For sorted coins $c_1\leq\cdots\leq c_C$, we have $D_{q+1}-D_q=c_{q+2}-c_{C-q}$. Hence $D_q$ decreases toward the middle and then increases. Its maximum occurs at an endpoint. There are at least two smallest coins, so that maximum is $2a-N\leq1$. The intervals for $q=1,\ldots,C-1$ therefore fill $[a,W-a]$. Choosing no coins or all coins gives the other two sums, and the minimum coin value excludes any other exterior sums.

Completeness of the interior for large $N$. The first differences are

and decrease. For $N\geq13$, the first maximizing indices satisfy $p,q\geq2$ and $N\geq2p+1,2q+1$. Indeed, when $N=2s$, $\Delta B_{s-1}=s(7-s)/2\leq0$; when $N=2s+1$, $\Delta B_s=-(s-2)(s+1)/2\leq0$. Also $\Delta F_t<\Delta B_t$.

Apply the coin lemma to the first construction at $t=p$. It fills

The left endpoint is at most $1$, so every positive target in the interior is attainable. The second construction at $t=q$ fills

Meanwhile, putting every positive vertex at depth $1$ and each negative vertex independently at depth $1$ or $2$ fills $[-S(N),0]$. The two intervals overlap, filling the negative interior as well. Therefore every integer in

is attainable.

The three candidates at either boundary. Consider the upper band $[R_N-p,R_N]$. We have $\Delta F_t-\Delta F_{t-1}=-(5t+2)$. Since $p$ is the first maximizer, $\Delta F_{p-1}>0$ and $\Delta F_p\leq0$, giving

If the number $t$ of negative records is outside $p-1,p,p+1$, even its optimum is outside the band. For these three counts, nonprefix record sets lose at least $4t+1>p$ and are excluded too. Any other modification of a prefix optimum loses at least $t+1$. When $t=p-1$, the first-maximizer convention gives $F_N(t)<R_N$, leaving a loss budget of at most $p-1=t$; the budget is also at most $t$ in the other two cases. Thus only $F_N(p-1),F_N(p),F_N(p+1)$ can occur in the band. The explicit constructions attain each candidate that lies there.

The lower band follows in the same way from $\Delta B_t-\Delta B_{t-1}=-5t$, using $q$ instead of $p$. Moving two indices away loses more than $5(q-1)$ or at least $5(q+1)$, both exceeding $q$. Nonprefix sets lose at least $4t-1>q$. Hence only $-B_N(q-1),-B_N(q),-B_N(q+1)$ can occur. This completes the reachability classification for $N\geq13$.