公式解説と同様に木の問題に帰着します。
その後、線形計画法として定式化し、双対問題を考えることで見通しが良くなります。

\(x_i\) を頂点 \(i\) での操作回数とすると次のように定式化できます。

\[\begin{aligned} &\mathrm{minimize}&\sum_{i=1}^NB_ix_i\\ &\mathrm{subject\ to}&\sum_{j:j\text{は}i\text{または}i\text{の祖先}}x_j\ge A_i,&&(1\le i\le N)\\ &&x_i\ge 0,&&(1\le i\le N)\\ \end{aligned}\]

双対を取ると次のようになります。

\[\begin{aligned} &\mathrm{maximize}&\sum_{j=1}^NA_jy_j\\ &\mathrm{subject\ to}&\sum_{k:k\text{は}j\text{または}j\text{の子孫}}y_k\le B_j,&&(1\le j\le N)\\ &&y_j\ge 0,&&(1\le j\le N)\\ \end{aligned}\]

これは、次のような問題に解釈できます。

• 頂点 \(i\) で操作を行うと報酬として \(A_i\) 貰える。
• 頂点 \(i\) の部分木の操作回数の合計は \(B_i\) 回以下。
• 制約を満たす限り何度でも操作できるとき、報酬の合計の最大値は？

この問題は次のように葉からボトムアップに貪欲に操作を行うことで解くことができます。

• 頂点 \(j\) において次のことを順に行う。
  • 子ノードの操作をマージした際に操作回数 \(B_j\) を超えてしまう分は報酬の小さい方から操作を取り消す。
  • 報酬が \(A_j\) より小さい操作は効率が悪いので取り消す。
  • 操作回数が \(B_j\) になるまで頂点 \(j\) で操作を行う。

操作の報酬の多重集合を優先度付きキューで管理し、子ノードのマージに weighted-union heuristic （データ構造をマージする一般的なテク）を適用することで時間計算量 \(O(N\log^2(N))\) で解くことができました。
さらに、 Leftist Heap などのマージを高速に処理できる優先度付きキューを使用することで時間計算量 \(O(N\log(N))\) を達成できます。