ABC244 G - Construct Good Path (600)
コンテスト中の解答
とりあえず全点を通るパスを作る
パスを前から順に見ていって点を通る数の偶奇が間違っていたら辺を足す
解説の解法
適当な全域木として考える
最小全域木でも良い
葉の方から再帰的に解く
子が無ければその要素のみ
子があれば子の結果の間を自身で繋ぐ
子の回数はこれ以降変わらなくなるので偶奇が違っている場合は自分→子を追加で追加する
問題:
https://atcoder.jp/contests/abc244/tasks/abc244_g
提出:
https://atcoder.jp/contests/abc244/submissions/30308927
#ABC244
#600pt
#G
#ABC
#AtCoder
#全域木
#DFS