DPテーブルの持ち方が少し違いますが、本質は公式解説と同じです。

木の問題に帰着するところまでは公式解説と同じです。

次のようなDPを考えます。

\(\mathrm{DP}[v][x]=\) 頂点 \(v\) に対応する区間に属するモンスター全ての体力を \(x\) 以下にするための必要魔力
求める答えは \(\mathrm{DP}[\text{根}][0]\) です。
\(H_v\) を頂点 \(v\) を”束ねる”モンスターの体力の最大値、\(P_v\) を頂点 \(v\) を”束ねる”モンスターのバリアの強さの最大値とします。例えば上の図の例なら根 \(v\) を”束ねる” のはバリアの強さが \(3\) である、体力が \(6\) と \(3\) のモンスターであり、\(P_v=3, H_v=6\) となります。
\(C(v,x)=\max(H_v-x,0)\) とします。つまり、頂点 \(v\) を”束ねる”モンスターの体力を \(x\) 以下にするために必要な攻撃回数を表します。
頂点 \(v\) に対応する区間に属するモンスター全ての体力を \(x\) 以下にするためには、区間全体に少なくとも \(C(v,x)\) 回の攻撃を行う必要があります。その回数を \(c+C(v,x)\) とすることで、DPの遷移は

\[\mathrm{DP}[v][x]=\max_{c \geq 0}\left((c+C(v,x))P_v+\sum_u \mathrm{DP}[u][x+c+C(v,x)]\right)\]

となります。

ここで、\(\mathrm{DP}[v][x]\) を \(x\) の関数だと思うことにします。すると、以下に述べるDPの遷移の詳細から、帰納法により、任意の \(v\) について、\(\mathrm{DP}[v][x]\) はある \(H_{v,1},H_{v,2},\ldots,B_{v,i},B_{v,2},\ldots\) を用いて \(\sum_i \max(H_{v,i}-x,0)B_{v,i}\) の形で書けることがわかります。
したがって、\(DP[v][*]\) のかわりに、この\(\{(H_{v,i},B_{v,i})\}\) を持つことでも情報は失われません。この方法でDPの計算をします。

DPの遷移式を \(x\leq H_v\) かどうかで分けて考えます。

\(x\leq H_v\) のとき、式を整理すると

\[\mathrm{DP}[v][x]=-P_vx+\max_{c \geq 0}\left(cP_v+\sum_u \mathrm{DP}[u][H_v+c]\right)\]

となります。max 内が \(x\) に依存しないため、この範囲では \(x\) の関数としては傾き \(-P_v\) の直線になります。（ここで、切片を求めるために、maxの部分の値を求める必要がないというのがミソです）

\(x\geq H_v\) のとき、式を整理すると

\[\mathrm{DP}[v][x]=\max_{c \geq 0}\left(cP_v+\sum_u \mathrm{DP}[u][x+c]\right)\]

となります。max 内の”意味”は「\(c\) を \(1\) 増やすごとに、\(P_v\) のコストがかかるかわりに、\(\sum_u \mathrm{DP}[u][*]\) の \(1\) つ右の値を使って良い」なので、\(\sum_u \mathrm{DP}[u][*]\) の傾きが \(-P_v\) より小さいときは、より右の値を見に行く方が良いです。 このことから、全体としては「\(x\) の関数としての傾きを \(\max(-P_v,\text{現在の値})\) に置き換える」となります。

以上を合わせると、\(\mathrm{DP}[v][x]\) は \(\sum_u \mathrm{DP}[u][x]\) をもとに、 「\(x\leq H_v\) 及び傾きが \(-P_v\) より小さい範囲を消して、傾き \(-P_v\) の直線に繋ぎ変える」とすることで得られます。

これは \(\{(H_{v,i},B_{v,i})\}\) の他に \(\sum_i B_{v,i}\) を持っておくことで、dictのマージテクにより、全体で \(O(N(\log N)^2)\) 時間で処理できます。