ABC067 D - Fennec VS. Snuke
解法
1とN以外の頂点を、
1から、Nを通らないとたどり着けない頂点
Nから、1を通らないとたどり着けない頂点
1とNどちらも、もう片方の頂点を通らずにたどり着ける頂点
の3種類に分けることができます。図で簡単に言うと次のようになります。
すると、1番左の部分は、すぬけが塗ることができず、逆に1番右の部分は、フェネックが塗ることはできません(閉路が無いため)。ので、左の部分はフェネックが確実に塗ることができ、一番右の部分はすぬけが確実にぬることができます。
ということは、この2つの部分は、お互いが最後に塗ればよく、それより先に真ん中の部分を塗って確保すべきです。
ここで、1とNを繋ぐ最短経路に注目します。
例えば、1とN、そしてその間の部分は上の図のようになっているとします。
すると、お互いの最善手は、1とNを繋いでいる頂点を真っ先にとることです。
今回、木しか与えられないという条件なので、1とNを繋いでいる頂点を自分の色で塗れば、そこについている部分木は確実に自分が塗ることができます。
これは、1とNを繋いでいる頂点すべてについて同じことが言えるため、ここをまず塗ることが最善になります。そこを塗り終えたら、あとはお互いが塗れる部分を塗りあっていき、先に塗れなくなった方が負けになります。
ということで、1とNを繋いでいる頂点の中心にある辺を切り、できた2つの部分木の頂点数を比較すれば、答えを求めることができます。
幅優先をまず行い、1とNの間の頂点を調べ、その中心の辺を切り(何かで記録します)、最後に2回、1とNからそれぞれ幅優先探索を行い、たどり着くことができる頂点数を比較すれば、答えが求まります。
