解法
木、とは書かれているのですが辺に重みがあるのでダイクストラをしてしまいました。
ある頂点と別の頂点の距離が奇数の場合、その部分は確実に色が異なります。
これを繰り返すと、結局はある頂点を一つ決めた際に、そこからの距離の偶奇を判定すればよくなります。
ということで、ある頂点を根としたときに、そこから距離が偶数の頂点は根と同じ色を、奇数の頂点は根と違う色を塗ればよいです。
あとは、ある根を適当に決めて、そこからほかの頂点への距離を求めていけばよいので、DFS,BFS,ダイクストラ法等を利用すればよいです。
感想
この手の問題をしっかりと処理できるのはいい傾向ですが、BFSでいい場面でダイクストラを書くことが多い気がするので、そういう部分で少しでもバグを生む可能性を減らしていけたらなぁと思います。
