AtCoder Beginner Contest 126：D - Even Relation
問題
解法
ある任意の頂点を 1 つ選び，その選んだ頂点からほかの全頂点との間の距離の偶奇で色を分ければよい．なぜならば，ある頂点 v, u と最初に選んだ頂点 r との距離がそれぞれ偶奇が等しければ， v -> r -> u の距離は当然偶数で，v と u の最も近い共通祖先 p と r の距離の 2 倍（これもまた偶数）を v -> r -> u の距離から引いたもの（すなわち v -> p -> u の距離）は偶数 - 偶数より偶数となり，v と u は同じ色で塗られているのは正しい状況であるから．これは任意の 2 頂点に関して言えるので，最初の方針は正しい．O(N)．
解答
