辺全体の集合を \(E ( \subseteq V \times V)\) と表し、公式解説のとおりに \(\mathtt{DP}_0, \mathtt{DP}_1, \mathtt{Ans}\) を定義すると、

\[ \mathtt{Ans} [k] = \min _ { i \lt k \lt j, (i, j) \in E } \mathtt{DP}_0 [ i ] + 1 + \mathtt{DP}_1 [ j ] \ ( 1 \le k \le N ) \]

が成立します。

これを計算するためには、\(\mathtt{Ans}\) を \(\infty\) で初期化しておき、区間 change min 作用で更新してけばよいです。

これはクエリをソートすることで区間「未初期化部分だけ上書きする」クエリに変換して union find を使うか、双対セグメント木で処理すれば \(O ( N M + E \log N )\) 時間で計算することができます。（さらに入力が隣接リストならば \(O ( E \log N )\) に改善します。）