問題 atcoder.jp 解法 コンテスト参加中 「DFS(深さ優先検索)だろ！こりゃACもらった！」 と思ったら、TLEで解けなくてガッカリだったー。 ので復習。 この問題、DFSで木を上方向に戻る処理まで再帰関数で実装してしまったんだが、1に戻って終わるのが前提の…

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…