atcoder.jp 考えたこと 条件は 個のが与えられ、は偶数である。 なので、の偶奇が分かればの偶奇が一意に定まる。 そこで枝によって作られるグラフを考えると連結部分のうち一か所が分かれば、連結部分は一意に定まる。 よって枝によって作られるグラフの連…

atcoder.jp 考えたこと 求めるグラフの条件は 同じ色に塗られた 任意の 2 頂点について、その距離が偶数である。 であるが、任意の2頂点間の距離を求めて、すべてが偶数かを確認する必要はない。 なぜなら考えるグラフは木なので、閉路を持たず、各頂点間の…