For each \(i = 1,\ 2,\ , \cdots,\ h_{max}\) , consider:

• Perform one operation on the intervals with which the cost to reduce the HP of all monsters with HP \(\ge i\) is minimum possible.

The total cost of the operations is the answer we want to find. Consider \(i\)’s from the largest. How much does the cost increase when we decrease \(i\) gradually? The optimal solution is to choose the node with smallest additional cost from the all nodes between \(i\) and the root. More specifically, what we want to do is

• Initialize with \(st[i]:=B_i\)
• Do the following on each \(i\), starting from largest \(A_i\) to smallest
  • Find the minimum \(st[j]\) when \(j\) moves on the path between \(i\) and the root, inclusive. Let the minimum value be \(m\). This is the optimal additional cost.
  • Subtract \(m\) from \(st[j]\) for all \(j\) on the path between \(i\) and the root, inclusive.

These operations, range addition and range get minimum, can be done by HLD + lazy segment tree, in \(O(N (\log N)^2)\) time.

AC code （PyPy3）