AtCoder Grand Contest 014 D - Black and White Tree
N頂点からなる木について、交互に白黒白と色を塗っていくゲームをする。最後に1回だけ、黒が隣接している白の点を一斉に黒にする。この時白が残っていれば白の勝ちである。最適に行動したときにどちらが勝つか求めよ。
木の葉が2個以上ある節が存在すれば勝ち確定である(※)。そうでない時は、頂点が2n個の直線状に並んでいるところについて、葉の一歩手前に白を置くと、黒は葉に置かないと「-○-○」(右端が葉)のような形を作られて白が勝ち確定であるので、葉に置くという行動が最適解になる。「-○-●」よってこのような形になったあと、この部分は無視してよく、結果として2n個の直線状に並んでいるところはどんどん頂点を削除していこう。そういう操作を続けていった結果、(※)の状態が現れた、もしくは1点のみになった時点で白の勝ち、それ以外は黒の勝ちである。
実装としてはdfsで直線上のところは頂点の偶奇をつけておき、そうでないところは子が奇数の点をカウントし、2個以上あったら白の勝ち確定、それ以外は奇数の数を親ノードに返す、みたいなことをする。O(N)。
