競技プログラミング用 知識集積所
ABC448D - Integer-duplicated Path
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
毎回経路探索をしていてはTLE。
それどころか、経路を最初に全部探索しても、数の重複があるかどうかのチェックだけですら普通にやるとTLEする。
というのは、直線の木で数値の重複がほとんどなかった場合、毎回数値一覧を作っていては頂点1からの距離だけ毎回かかってしまう。
かといって、数値一覧を頂点情報としてコピーしていっても同様。
それどころか、経路を最初に全部探索しても、数の重複があるかどうかのチェックだけですら普通にやるとTLEする。
というのは、直線の木で数値の重複がほとんどなかった場合、毎回数値一覧を作っていては頂点1からの距離だけ毎回かかってしまう。
かといって、数値一覧を頂点情報としてコピーしていっても同様。
そこで、数値一覧を使いまわししながら深さ優先探索※をする。
まず、頂点1からスタートする。
ある頂点に入った時に、数値一覧と重複数を更新し、頂点が条件を満たすかどうかを確認する。
その後、子を順に探索する。
それが終わった時に、更新した数値一覧と重複数を元に戻す。
これで、全頂点について、O(N)で（数値一覧にmap※などを用いたらO(NlogN)で）調査でき、間に合う。
まず、頂点1からスタートする。
ある頂点に入った時に、数値一覧と重複数を更新し、頂点が条件を満たすかどうかを確認する。
その後、子を順に探索する。
それが終わった時に、更新した数値一覧と重複数を元に戻す。
これで、全頂点について、O(N)で（数値一覧にmap※などを用いたらO(NlogN)で）調査でき、間に合う。
