AT_agc014_d [AGC014D] Black and White Tree

[problemUrl]: https://atcoder.jp/contests/agc014/tasks/agc014_d $ N $ 頂点からなる木があり、頂点には $ 1 $ から $ N $ の番号がついています。 また、 $ N-1 $ 本の辺の内、$ i $ 本目の辺は頂点 $ a_i $ と頂点 $ b_i $ を結んでいます。 はじめ、どの頂点にも色がついていません。 高橋君と青木君は各頂点に色を塗ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。 - 頂点の中から、まだ色がついていない頂点を一つ選ぶ。 - その後、高橋君ならその頂点を白色に、青木君ならその頂点を黒色に塗る。 次にすべての頂点に色がついた後、高橋君と青木君は以下の手順を一度だけ行います。 - 黒色の頂点に隣接している白色の頂点をすべて黒色に塗りかえる。 ただし、この操作はある頂点から順に操作を行っていくわけではなく、当該頂点すべてに対して同時に行うことに注意してください。 最終的に白色の頂点が残っていれば高橋君の勝ちであり、全て黒色の頂点であれば青木君の勝ちです。 二人が最適に行動したとき、どちらが勝つか求めてください。

N/A

N/A

### 制約 - $ 2\ ≦\ N\ ≦\ 10^5 $ - $ 1\ ≦\ a_i,b_i\ ≦\ N $ - $ a_i\ ≠\ b_i $ - 入力で与えられるグラフは木である。 ### Sample Explanation 1 ゲームの一例を示す。 - 高橋君がまず頂点 $ 2 $ を白色に塗る。 - その後、青木君が頂点 $ 1 $ を黒色に塗る。 - 最後に高橋君が頂点 $ 3 $ を白色に塗る。 このように進んだ場合、最後の操作で頂点 $ 1,2,3 $ の色がそれぞれ黒、黒、白となるので、高橋君の勝ちとなる。