公式解説とは異なるアルゴリズムです。こちらのほうが高速である場合があります。

公式解説の動的計画法の漸化式を拝借します。ただし、 \(X\) を不定として \(\text{dp}\) の代わりに \(\text{dp}_X\) を使います。

\[ \begin{aligned} &&& \text{dp}_X[v]:=\max\left\lbrace\sum_{c\in \mathcal{C}_v}\text{dp}_X[c]-1,0\right\rbrace+f(X,A_v). \\ ただし、 &&& f(X,A_v)=\left\lbrace{\begin{aligned} 1 && (X\leq A_v) \\0 && (A_v \lt X)\end{aligned}}\right. . \end{aligned} \]

\(X\) の関数 \(\text{dp}_X[v]\) は、 \(X\) の変化に対して単調です。よって、 \(\text{dp}_X[v]\) の値が変化する \(X\) の値の多重集合を管理することで、すべての \(X\) に対して一度に計算できます。

漸化式の計算のために必要になる処理を列挙します。

• \(\sum_{c\in \mathcal{C}_v}\text{dp}_X[c]\) は、多重集合のマージに相当します。
• \(\max\left\lbrace x-1,0\right\rbrace\) は、多重集合が空でなければ最大の要素を \(1\) つ取り除くことに相当します。
• \(x+f(X,A _ v)\) は、値 \(A _ v\) を多重集合に追加することに相当します。

よって、これを優先度付きキュー（heap）を用いて処理します。

std::priority_queue を用いて、マージに Weighted Union Heuristic を適用することで全体の計算量を \(O(N (\log N)^2)\) とできます。

leftist heap など、 meldable heap と呼ばれる構造を用いると、計算量を \(O(N \log N)\) とできます。

解答例