Educational DP Contest:G - Longest Path
問題
解法
dp(i) := 頂点 i から始まるパスで最長のものの長さ
と定義する.このとき,
dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点)
と漸化式が立つ.答えは dp(i) (1 <= i <= N) の最大値.状態数 O(N),遷移 O(N - 1) だけれども,各辺は高々 1 回しか見ないので O(N).
解答
dp(i) := 頂点 i から始まるパスで最長のものの長さ
と定義する.このとき,
dp(i) = max( dp(v) + 1 ) (v は頂点 i から到達できる任意の頂点)
と漸化式が立つ.答えは dp(i) (1 <= i <= N) の最大値.状態数 O(N),遷移 O(N - 1) だけれども,各辺は高々 1 回しか見ないので O(N).