NIKKEI Programming Contest 2019 D - Restore the Tree
トポロジカルソートして 「dp[i] = max(dp[i], dp[i + 1] + 1)」を後ろから計算する。これは何をやっているかというと、葉を0とし、各頂点から一番遠い葉までの距離が入っている。
問題文で追加されているという辺は必ず子へのショートカットとなる辺なので、子からみた直接の親となる頂点は、親候補→子 となるエッジのある親候補のうち、dp[親候補]が最小の頂点が親になる。
ちなみに dp[親] = dp[子] + 1 は誤りである。なぜなら、親から見た別の子がより遠い葉を持っている可能性があるからである。
計算量はトポロジカルソートが支配項で O(N+M)。
