m_99 さんの解説 の冒頭の考察を使います。

体力が大きい方から順に処理することにすると、各ステップでのコストはどれだけ増加するでしょうか？見ているノードから根までの Path の中で最もコストの増加が少ないものを選べば良いです。具体的には下記を行いたいです。

• \(st[i] := B_i\) で初期化する
• \(A_i\) が大きい方から順に下記を行う
  • \(i\) から根までの Path 上にある頂点 \(j\) についての \(st[j]\) の最小値（ \(m\) とする）を取得する（この \(m\) がコストの増加値になる）
  • \(i\) から根までの Path 上にある頂点 \(j\) について \(st[j]\) から \(m\) を引く

これは木上の区間加算・区間 min 取得の処理なので、 HLD + 遅延セグ木などで実装できます。 計算量は \(O(N (\log N)^2)\) です。

AC コード （PyPy3）