ABC126D

https://gyazo.com/e04b1343acc9d7bf636fa218acfe0162

考えたこと

ある一点に注目する、これを白とする

その点から1ステップでたどれる点は黒でなければならない

黒から1ステップでたどれる点は白でなければならない

というわけでDFSで交互に塗ればOK

これでいい理由

任意の2点への根からの距離の合計とその2点の距離の偶奇は一致するから

似たような処理を何かで見た気がするがなんだったかなー