水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

Educational DP Contest:G - Longest Path

問題

atcoder.jp

解法

dp(i) := 頂点 i から始まるパスで最長のものの長さ

と定義する.このとき,

dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点)

と漸化式が立つ.答えは dp(i) (1 <= i <= N) の最大値.状態数 O(N),遷移 O(N - 1) だけれども,各辺は高々 1 回しか見ないので O(N).

解答

atcoder.jp

f:id:babcs2035:20190107170027p:plain