ABC126 D Even Relation
頂点1を根とした根つき木を考える. すると, 根からの距離の偶奇で色を分ければよい(これはLCAを用いた2頂点間の距離の求め方が頭にあれば導ける). 根からの距離はDFSで走査することにより求められる.
実装例:
https://atcoder.jp/contests/abc126/submissions/19565407