DPまとめコンテスト/G - Longest Path - 競技プログラミング用 知識集積所【7/18更新】

---

問題

DP-G

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• 隣接リスト（未作成）
• トポロジカルソート（未作成）

考え方

木（未作成）の高さを求める深さ優先探索（未作成）と同じ発想でやればよい。

つまり、トポロジカルソート（未作成）をして、後ろから順に

• 出次数が0なら高さ0
• 出次数が1以上なら、その行先の高さの最大値+1

を順に計算すればよい。
（この問題だけなら正順で配るDPした方が楽かもしれない）

あとは、全頂点の高さの最大値を出すだけ。
動的計画法本体よりも、トポロジカルソート（未作成）をすることの方が大変かもしれない。

解答例

解答例

注意点

別解