問題
atcoder.jp
解法
コンテスト参加中
「DFS(深さ優先検索)だろ！こりゃACもらった！」
と思ったら、TLEで解けなくてガッカリだったー。
ので復習。
この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の問題。
なので、戻るに決まってるので、木構造の一番深いところまで行くところまで計算したら、あとの戻りは自明で決まる。
ゆえに下に行った直後に、元の都市への戻りを追加してしまえば、一番深いところまでの片道の計算で済む。
実装
実行結果
PyPy3(7.3.0) AC 1169ms
Python(3.8.2) AC 1151ms
再帰関数よびまくりだが、PyPyでもPythonでも、そこまで実行速度に差がないね。
